您如何迭代属于同一大小 n 域的 m 个变量的所有配置? [英] How do you iterate over all configurations of m variables belonging to the same domain of size n?

问题描述

我的解决方案已添加到问题的末尾.感谢您的提示.

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

我只是举个例子.假设我有一个长度为 n:

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

如果我想遍历三个元素的所有配置，我只需添加另一层 for 迭代:

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

如果元素的数量是由用户给出的(比如 m)，而我们不知道它到底是什么?那我该怎么写呢?

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

回答解决方法是这个函数:

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("
");
        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:

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 

推荐答案

你可以简单地使用 递归.

一些伪代码:

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 语句触发时，我们将拥有一个包含排列的数组，我们可以用它做任何事情.

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

使用 someFunction(inputArray, n, 0, desiredDepth) 调用.

这篇关于您如何迭代属于同一大小 n 域的 m 个变量的所有配置?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！