How do you iterate over all configurations of m variables belonging to the same domain of size n?

Question

EDIT: My solution is added to the end of the question. Thanks for the hint.

I'll just go with an example. Suppose I have an array with length n:

arr = { 1, 4, 8, 2, 5, ... }

If I want to traverse all combinations of TWO elements I would write:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // do something with arr[i] and arr[j]
    }
}

I If I want to traverse all configurations of THREE elements I would simply add another layer of for iteration:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // do something with arr[i] and arr[j]
        }
    }
}

What if the number of elements is given by user (say m), and we don't know exactly what it is? What should I write then?

(I couldn't figure out the best title for this question. And the tags are not accurate either. Help me with these too, if you want.)

Answer The solution is this function:

void configurations(int depth, int* array, int length, int* indices, int curDepth) {
    if (curDepth == 0) {
        for (int i = 0; i < depth; i++) {
            printf("%d ", indices[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 0; i < length; i++) {
        indices[curDepth - 1] = i;
        configurations(depth, array, length, indices, curDepth - 1);
    }
}

The usage of the function above is shown below:

int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int configSize = 3;
int* indices = new int[configSize];
configurations(configSize, a, 9, indices, configSize);

The console will show all configurations of the given size of the elements in the array:

What you're trying to do is simply walk through all the possible combinations of `n` elements, `k` by `k` -- being `k` and `n` given as input parameters. [Here](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) are dozens of algorithms for doing so. — Rubens, Jan 01 '14 at 12:25

Bernhard Barker · Answer 1 · 2014-06-08T20:34:57.740

You can simply use recursion.

Some pseudo-code:

void someFunction(int[] arr, int n, int depth)
{
  if (depth == 0)
  {
    // do something with the stored elements
    return;
  }

  for (int i = 0; i < n; i++)
  {
    // store arr[i]
    someFunction(arr, n, depth-1);
  }
}

There are a few ways to store arr[i]. One way could be to pass an array of size initialDepth down via the recursive call, along with the current index in that array. We increase the index on every recursive call, and put arr[i] at the current index. Then, when the depth == 0 if-statement triggers, we'll have an array containing a permutation, which we could do whatever with.

This, as your code, would repeat elements (i.e. one permutation will consist exclusively of the first element repeated a few times). If you wish to avoid this, you can instead swap the first element with each other element at the first step, then recurse, swapping the second element with each other element at the second step, and so on.

void someFunction(int[] arr, int n, int pos, int depth)
{
  if (pos == depth)
  {
    // do something with the elements in arr from 0 to pos
    return;
  }

  for (int i = pos; i < n; i++)
  {
    // swap arr[pos] and arr[i]
    someFunction(arr, n, pos+1, depth);
    // swap arr[pos] and arr[i] back
  }
}

Call with someFunction(inputArray, n, 0, desiredDepth).

Thank you. I've edited the question. My own solution based on yours is attached to the end of my original question. Please tell me the "native" way to post a solution in Stack Overflow. I'm quite new to it. Thanks! — Yuhuan Jiang, Jan 02 '14 at 03:24
If you feel one of the answers already sufficiently answers your question, you can simply [accept](http://stackoverflow.com/help/someone-answers) it. Otherwise, you can post your own solution as another answer to the question, and either accept the answer that most helped you get your solution, or your own answer if there was no such answer. — Bernhard Barker, Jan 02 '14 at 12:32

Tongfei Chen · Answer 2 · 2014-01-01T12:31:19.067

0

Use backtracking (depth-first search). The general idea will be something like this:

void Generate(int n) {
    if ((0..n).count(i => used[i]) >= NUMBER_OF_ELEMENTS_DESIRED_FOR_A_PERMUTATION) {
        print this permutation;
        return;
    }
    used[n] = true;
    foreach (int next in (0..n).where(i => !used[i])) 
        Generate(next);
    used[n] = false;
}

edited Jan 01 '14 at 12:31

answered Jan 01 '14 at 12:25

Tongfei Chen

613
4
14

score 0 · Answer 3 · answered Jun 08 '14 at 20:48

You can be use recursion, Something like this:

public static void main(String[] args) {
        char[] alphabet = new char[] {'a','f','j'};
        possibleStrings(2, alphabet,"");
    }

    public static void possibleStrings(int maxLength, char[] alphabet, String curr) {
        if(curr.length() == maxLength) {
            System.out.println(curr);
        } else {
            for(int i = 0; i < alphabet.length; i++) {
                String oldCurr = curr;
                curr += alphabet[i];
                possibleStrings(maxLength,alphabet,curr);
                curr = oldCurr;
            }
        }
    }

How do you iterate over all configurations of m variables belonging to the same domain of size n?

3 Answers3

Linked