How to iterate over every permutation of independent choices?

Question

Let's say I have a list [x1, x2, x3] where x1, x2, and x3 can take on any value between 1 and 5.

I want to iterate over every possible list that can be created (From [1, 1, 1], [1, 1, 2], . To [5, 5, 5]). This is an easy problem with only 3 elements in the list.

You can do something like this:

for x = 1; x <= 5; x++;
    for y = 1; y <= 5; y++;
        ...
          for q = 1; q <= 5; q++;
              create list [x, y, ..., q];
              do something with the list;

However, how do you iterate over every possible list where the number of elements is over like 10?

Edi: I've added Java as a constraint. I just want to see how this would be done without too many fancy library calls.

Edit2: What I am really looking for is some algorithm to do this, not what sort of libraries can be used to do it. But what I'm looking for is really a language-independent algorithm.

I had to do something similar to this once. I found the "easiest" thing to do was to generate code (which isn't that difficult). Given the number of elements you _know_ what the loop structure should look like, it's just a matter of printing the right amount of for loops. So you can write code to generate the proper code, then run that generated code. You could make this "automatic" using reflection. — Jared, Sep 21 '14 at 02:33
One of undoubtedly dozens of duplicates: http://stackoverflow.com/questions/10419382/generating-the-cartesian-power-of-a-set — David Eisenstat, Sep 21 '14 at 03:32
Thanks for your insight David, I didn't realize this problem had a formal name else I would have probably found my solution. — CowZow, Sep 25 '14 at 18:37

score 2 · Answer 1 · answered Sep 19 '14 at 01:00

Using Guava you can do it easily:

     public static void main(String[] args) {

         int lowerBound = 1;
         int upperBound = 5;
         int setSize=3;

         ContiguousSet<Integer> integers = ContiguousSet.create(Range.closed(lowerBound, upperBound), DiscreteDomain.integers());
         List<Set<Integer>> sets = Lists.newArrayList();

         for (int i = 0; i < setSize; i++) {
             sets.add(integers);
         }

         Set<List<Integer>> cartesianProduct = Sets.cartesianProduct(sets);
         for (List<Integer> list : cartesianProduct) {
             System.out.println(list);
         }
     }

Which prints:

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 1, 5]
...  
[5, 5, 4]
[5, 5, 5]

score 2 · Accepted Answer · answered Sep 23 '14 at 12:29

Logic : In arr[x1 x2 x3]; all x1, x2, x3 can have values from 1 to 5. Which means every position in array can have value from 1 to 5. For a value at current position all the values are possible at next position.

suppose at 0 position of array value stored is 1.

[1 _ _] _ represent there is no value.

values for the next position : [1 1 _] , [1 2 _] ,[1 3 _] ,[1 3 _] ,[1 4 _],[1 5 _].

So iterate over current position to store the different possible values from 1 to 5 at current position and for each value call the permutate function again with current position value incremented by 1 for iterating all possible values from 1 to 5 at next position .

Code :

public class permutation {

    static int limit;
    public static void permutate(int arr[],int curPos)
    {
        int i;
        if(curPos==arr.length)
        {
            for(i=0;i<arr.length;i++)
            {
                System.out.print(arr[i] + "\t");
            }
            System.out.println("");
            return;
        }

        for(i=1;i<=limit;i++)
        {
            arr[curPos]=i;
            permutate(arr,curPos+1);
        }  

    }


    public static void main(String[] args) {
        int arr[] = new int[3];
        limit = 5;
        permutate(arr,0);
    }

}

Output :

Thanks. I made the "limits" an array, too. So I could have [1..5] [1..2] [1..9] for example. You just need to use `for(i = 1; i < limits[curPos]; i++)` then. I need that to permutate combinations of players. A text contains placeholders like `any` or `male` or `female` and the list of males has a different length compared to the list of females. — KYL3R, Aug 21 '21 at 18:34

score 1 · Answer 3 · answered Sep 14 '14 at 02:36

1

At least in python (You should specify language if it's a constraint):

>>> from itertools import permutations as permu
>>> for i in permu(range(5), 3):
...     print i 
... 
(0, 1, 2)
(0, 1, 3)
(0, 1, 4)
(0, 2, 1)
(0, 2, 3)
(0, 2, 4)
(0, 3, 1)
....

answered Sep 14 '14 at 02:36

DOOM

1,170
6
20

score 1 · Answer 4 · answered Sep 14 '14 at 03:21

In recursive solution you don't have to sort the list every time. Giving sorted list to recursive function must be sifficient.
To do so, I've written this piece of C# code. Length of output result will be determined by len. Just remember that input length must be equal or bigger than len:

// Input must be sorted, Result must be initialized to empty list
void Iterate(List<int> input, int len, List<int> result)
{
  if(result.Count == n)
    print result
  else
    foreach (var i in input)
      Iterate(input, len, result.Append(num).ToList())
}

Peter O. · Answer 5 · 2014-09-21T02:54:43.830

Use this algorithm.

Input: X is the minimum number, Y is the maximum number, and Z is the number of independent choices.

Create an array of size Z, with each element equal to X. Call it Permutation.
Loop:
- Add a copy of Permutation to the list of permutations.
- Set J to Z minus 1.
- Loop:
  - Add 1 to Permutation[J]. If Permutation[J] is now Y or less, break.
  - Set Permutation[J] to X.
  - Subtract 1 from J. If J is now less than 0, return the list of permutations.

score 0 · Answer 6 · answered Sep 22 '14 at 12:06

Must be classic algorithm. But it always fun to write it from scratch. Here is Java class accepting data set and result list size parameters. Core method is generate(). Also lists might be copied on demand (to be more functional style).

import com.google.common.collect.Maps;
import org.apache.commons.lang.ArrayUtils;

import java.util.Map;

public class PermutationGenerator {

    private int listValuesSize;

    private int resultListSize;

    private String[] currentList;

    private Map<String, String> nextValue = Maps.newHashMap();

    private int permutations = 0;

    public PermutationGenerator(String[] dataSet, int resultListSize) {
        this.listValuesSize = dataSet.length;
        this.resultListSize = resultListSize;
        init(dataSet);
    }

    private void init(String[] dataSet) {

        // rolling values
        String previous = dataSet[0];
        for (int valuesIndex = 1; valuesIndex < dataSet.length; valuesIndex++) {
            nextValue.put(previous, dataSet[valuesIndex]);
            previous = dataSet[valuesIndex];
        }
        nextValue.put(dataSet[dataSet.length - 1], dataSet[0]);

        // init
        currentList = new String[resultListSize];
        for (int i = 0; i < resultListSize; i++) {
            currentList[i] = dataSet[0];
        }
    }

    public void generate() {
        generate(0, resultListSize - 1);
    }

    private void generate(int from, int to) {
        if (from > to) {
            return;
        }

        for (int i = 0; i < listValuesSize; i++) {
            if (from == to) {
                processList(currentList);
            } else {
                generate(from + 1, to);
            }
            roll(from);
        }
    }

    private void roll(int position) {
        currentList[position] = nextValue.get(currentList[position]);
    }

    private void processList(String[] list) {
        permutations++;
        System.out.println(ArrayUtils.toString(list));
    }

    public static void main(String... args) {
        PermutationGenerator generator = new PermutationGenerator(new String[]{"1", "2", "3", "4", "5"}, 3);
        generator.generate();
        System.out.println(generator.permutations);
    }

}

How to iterate over every permutation of independent choices?

6 Answers6