CODEWITHSUNDEEP
javaalgorithmcombinations
spyr03
spyr03

Reputation: 882

Print all possible choices from 1 to x

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

Upvotes: 1

Views: 133

Answers (3)

spyr03
spyr03

Reputation: 882

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]++;
            }
        }

Upvotes: 0

Adam Coath
Adam Coath

Reputation: 26

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?

Upvotes: 1

samgak
samgak

Reputation: 24427

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.

Upvotes: 1

Related Questions