java - 不使用数组从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);
    }
}

希望评论能够引导您理解算法。