數組序列從1到N的排列方法，無數組，java

Question

請幫助我找出如何編寫打印所有可能的1到N數字組合的方法。我不能使用數組，集合或字符串。 我需要這樣的輸出（3）：

[1] [2] [3] 
[1] [3] [2] 
[2] [1] [3] 
[2] [3] [1] 
[3] [2] [1] 
[3] [1] [2] 

有使用數組來寫這樣的方法沒有任何問題：

public class Test { 

static void permute(int[] a, int k) { 
    if (k == a.length) { 
     for (int i = 0; i < a.length; i++) { 
      System.out.print(" [" + a[i] + "] "); 
     } 
     System.out.println(); 
    } else { 
     for (int i = k; i < a.length; i++) { 
      int temp = a[k]; 
      a[k] = a[i]; 
      a[i] = temp; 

      permute(a, k + 1); 

      temp = a[k]; 
      a[k] = a[i]; 
      a[i] = temp; 
     } 
    } 
} 

public static void main(String args[]) { 
    int N = 3; 
    int[] sequence = new int[N]; 

    for (int i = 0; i < N; i++) { 
     sequence[i] = i + 1; 
    } 

    permute(sequence, 0); 

} 

}

在此先感謝您的幫助！

UPD 1.我也想寫點東西像這樣（但沒有成功）：

public class Combinations { 

private static int change; 

public void doIt(int n, int pos) { 

    if (pos == n) { 
     for (int f = 1; f <= n; f++) { 
      System.out.print(f + " "); 
     } 
     System.out.println(""); 
    } else { 

     for (int i = pos; i < n; i++) { 
      change = pos; 
      System.out.print(change + " "); 
      pos = i; 
      System.out.print(pos + " "); 
      i = change; 
      System.out.print(i + " "); 
      System.out.println(""); 

      doIt(n, pos + 1); 

      change = pos; 
      System.out.print(change + " "); 
      pos = i; 
      System.out.print(pos + " "); 
      i = change; 
      System.out.print(i + " "); 
      System.out.println(""); 

     } 
    } 
} 
} 

Answer 1

爲此，您可以使用Factoradics（你可以看到一個實現here），或生成所有排列的Knuth's L-Algorithm 。以下是以後的（工作到位）的實現：

public class Perm { 
    private static int factorial(int n) { 
     int fact = 1; 
     for (int i = 1; i <= n; i++) { 
      fact *= i; 
     } 
     return fact; 
    } 

    private static void swap(int[] elements, int i, int j) { 
     int temp = elements[i]; 
     elements[i] = elements[j]; 
     elements[j] = temp; 
    } 

    /** 
    * Reverses the elements of an array (in place) from the start index to the end index 
    */ 
    private static void reverse(int[] array, int startIndex, int endIndex) { 
     int size = endIndex + 1 - startIndex; 
     int limit = startIndex + size/2; 
     for (int i = startIndex; i < limit; i++) { 
      // swap(array, i, startIndex + (size - 1 - (i - startIndex))); 
      swap(array, i, 2 * startIndex + size - 1 - i); 
     } 
    } 

    private static void printSequence(int[] sequence) { 
     for (int i = 0; i < sequence.length; i++) { 
      System.out.printf("%d, ", sequence[i]); 
     } 
     System.out.println(); 
    } 

    /** 
    * Implements the Knuth's L-Algorithm permutation algorithm 
    * modifying the collection in place 
    */ 
    private static void permutations(int[] sequence) { 
     final int N = sequence.length; 
     // There are n! permutations, but the first permutation is the array without 
     // modifications, so the number of permutations is n! - 1 
     int numPermutations = factorial(N) - 1; 

     // For every possible permutation 
     for (int n = 0; n < numPermutations; n++) { 

      // Iterate the array from right to left in search 
      // of the first couple of elements that are in ascending order 
      for (int i = N - 1; i >= 1; i--) { 
       // If the elements i and i - 1 are in ascending order 
       if (sequence[i - 1] < sequence[i]) { 
        // Then the index "i - 1" becomes our pivot index 
        int pivotIndex = i - 1; 

        // Scan the elements at the right of the pivot (again, from right to left) 
        // in search of the first element that is bigger 
        // than the pivot and, if found, swap it 
        for (int j = N - 1; j > pivotIndex; j--) { 
         if (sequence[j] > sequence[pivotIndex]) { 
          swap(sequence, j, pivotIndex); 
          break; 
         } 
        } 

        // Now reverse the elements from the right of the pivot index 
        // (this nice touch to the algorithm avoids the recursion) 
        reverse(sequence, pivotIndex + 1, N - 1); 
        break; 
       } 
      } 

      printSequence(sequence); 
     } 
    } 

    public static void main(String... args) { 
     final int N = 3; 
     int[] sequence = new int[N]; 
     for (int i = 0; i < N; i++) { 
      sequence[i] = i + 1; 
     } 

     printSequence(sequence); 
     permutations(sequence); 
    } 
} 

希望的意見指導你在算法的理解。