Permutation method for number sequence from 1 to N without arrays, java

Question

Please help me to find out how to write method that prints all possible combination of numbers from 1 to N. I can't use arrays, collections or strings. I need output like that (for 3):

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

There is no problem to write such method using array:

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);

}

}

Thanks in advance for any help!

UPD 1. I'm also trying to write something like this (but unsuccessful):

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("");

        }
    }
}
}

en.wikipedia.org/wiki/Factorial_number_system might prove useful. — rici
– rici, Commented Apr 4, 2015 at 19:51
Hint: Use print inside your method, without newline except where appropriate. — RealSkeptic
– RealSkeptic, Commented Apr 4, 2015 at 19:53
@Floris I agree with you but I need some hint for this. In UPD I wrote my attempt of such method. I have no idea how to make it work. — Vasyl Hoshovsky
– Vasyl Hoshovsky, Commented Apr 4, 2015 at 20:16
@VasylHoshovsky At the risk of sounding repetitive -- so long as by collections is meant classes within Java's collections framework, then it is probably in principle trivial (though in practice somewhat cumbersome) to reproduce your array-using solution with, say, BitSets. But otherwise I am not quite sure whether the problem has a solution, though my intuition is that it should be doable. =( — Jae Heon Lee
– Jae Heon Lee, Commented Apr 5, 2015 at 20:09

dinox0r · Accepted Answer · 2015-04-04 23:46:46Z

For this you could use Factoradics (you can see an implementation here) or the Knuth's L-Algorithm that generates all permutations. The following is an implementation of the later (works in place):

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);
    }
}

Hope the comments guide you in the understanding of the algorithm.

Collectives™ on Stack Overflow

Permutation method for number sequence from 1 to N without arrays, java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related