Print all possible choices from 1 to x

Question

Is there a way to print all the possible choices of 1 to x where there are no repeated numbers and for variable amount of numbers?

So basically if x = 10, and n (the length of the list) = 5

[1,2,3,4,5],  [1,2,3,4,6]...
[2,1,3,4,5]...
[10,9,8,7,6]

Where the order of producing these lists doesn't matter, so the second list in the example could be printed last if it is convinient

EDIT

What I have tried so far, but it isn't easy to change

    for (int a = 1; a < x; a++) {
        Set<Integer> data = new HashSet<>();
        data.add(a);

        for (int b = 1; b < x; b++) {
            if(data.contains(b)) continue;
            data.add(b);
            for (int c = 1; c < x; c++) {
                if(data.contains(c)) continue;
                data.add(c);
                for (int d = 1; d < x; d++) {
                    if(data.contains(d)) continue;
                    data.add(d);
                    for (int e = 1; e < x; e++) {
                        if(data.contains(d)) continue;
                        //code
                    }
                }
            }
        }

http://stackoverflow.com/questions/20906214/permutation-algorithm-for-array-of-integers-in-java There's a solution to what you're going for — SexmanTaco, Jun 05 '15 at 01:49
@sstan nested loops that have to be added in every time, and adding the numbers to a set, if the set contains the number continuing to the next iteration — spyr03, Jun 05 '15 at 02:03
Please put the code that you tried for. Then we could help you better. — Francisco Romero, Jun 05 '15 at 02:13
@Error404 if I want to add more numbers I have to manually type out another nested loop, and while it does all permutations, to me the inverse of the entire list is unnecessary, so [1,2,3], [2,1,3], [1,3,2] are fine, while [3,2,1], [3,1,2], [2, 3, 1] are not needed if the above are generated — spyr03, Jun 05 '15 at 02:29

score 1 · Answer 1 · answered Jun 05 '15 at 02:27

Here's some code that finds all the possible selections without relying on storing the previously generated selection and checking if you have already output them:

public static void permuteArray(int[] array, int start) {
    if (array.length == start) {
         System.out.println(Arrays.toString(array));
    } else {
        for (int i = start; i < array.length; i++) {
            int temp = array[i];
            array[i] = array[start];
            array[start] = temp;
            permuteArray(array, start + 1);
            temp = array[i];
            array[i] = array[start];
            array[start] = temp;
        }
    }
}
public static void makeCombinations(int[] array, int startElement, int minValue, int maxValue, int length, boolean permute)
{
    // iterate through all values from minValue to maxValue minus the remaining spaces
    int remainingSpacesAfterThisOne = (length - 1) - startElement;
    for(int i = minValue; i <= (maxValue - remainingSpacesAfterThisOne); i++)
    {
        array[startElement] = i;
        if(startElement < (length - 1))
           makeCombinations(array, startElement + 1, i + 1, maxValue, length, permute);
        else
        {
            if(permute)
                // print out all permutations of this array:
                permuteArray(array, 0);
            else
                // print out the combination
                System.out.println(Arrays.toString(array));
        }
    }
}

public static void makeCombinations(int max, int length, boolean permute)
{
    int[] array = new int[length];
    makeCombinations(array, 0, 1, max, length, permute);
}

public static void main (String[] args)
{
    makeCombinations(10, 5, true);
}

The code generates all possible selections of length non-repeating numbers where the numbers in the selection are in ascending order, and optionally finds all the possible permutations of those selections.

If you have a max value of 10 and a length of 5, and your selection is in ascending order, then for the first item you can only choose a number from 1 to 6 inclusive (or else you won't have enough numbers to fill out the rest of the selection without repeating one or going out of ascending order). So the algorithm iterates over the possible legal values for the first item, then for each value recursively generates the possible selections that can make up the remainder of the list, enforcing ascending order by passing in the first value plus one as the min value.

Once there are no more values to generate, recursion stops and then the ascending-order selection can be permuted using a simple recursive permutation function to find all possible orderings.

score 1 · Accepted Answer · answered Jun 05 '15 at 02:31

1

It looks like you have a solution. Now you just need to be able to handle arbitrary values of n. What if instead of having n variables a,b,c,... you stored those values in an Array[n]? Could you simulate having n loops?

answered Jun 05 '15 at 02:31

Adam Coath

26
2

Like an old counter that when a number reaches max it resets to 0 and the one to its left increments? – spyr03 Jun 05 '15 at 02:42

score 0 · Answer 3 · edited May 23 '17 at 11:51

The code I came up with on Adam's suggestion

    int[] array = new int[len];
    Arrays.fill(array, 1);

    while(array[0] < X) {
        System.out.println(Arrays.toString(array));

        //CODE

        array[len-1]++;
        for(int a = len-1; a > 0; a--) {
            for(int b = a-1; b >= 0;) {
                if(array[a] == array[b]) {
                    array[a]++;
                } else b--;

            }

            if(array[a] >= X) {
                array[a] = 1;
                array[a-1]++;
            }
        }

Print all possible choices from 1 to x

3 Answers3