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

Question

EDIT: My solution is added at the end of the question. Thanks for the tip.

I will just give an example. Suppose I have an array of length n:

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

If I want to go through all the 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 foriteration layer :

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 set by the user (say m), and we don’t know exactly what it is? What should I write then?

(I could not figure out a better name for this question. And the tags are not exact either. Help me with them 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);
    }
}

:

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

:

0 0 0 
1 0 0 
2 0 0 
3 0 0 
4 0 0 
...
5 8 8 
6 8 8 
7 8 8 
8 8 8 

Answer 1

recursion.

:

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

arr[i]. - initialDepth . arr[i] . , depth == 0 if-statement, , , .

---

, , (.. , ). , , ..

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

someFunction(inputArray, n, 0, desiredDepth).

Answer 2

( ). :

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

Answer 3

You can 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;
            }
        }
    }