arrays - 您如何迭代属于同一大小为 n 的域的 m 个变量的所有配置？

Question

编辑:我的解决方案添加到问题的末尾。感谢提示。

我只是举个例子。假设我有一个长度为 n 的数组:

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

如果我想遍历两个元素的所有组合，我会这样写:

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

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

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)，而我们不知道它到底是多少怎么办？那我该怎么写呢？

(我想不出这个问题的最佳标题。而且标签也不准确。如果你愿意，也可以帮我解决这些问题。)

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

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

---

作为您的代码，这将重复元素(即一个排列将仅由重复几次的第一个元素组成)。如果您希望避免这种情况，您可以改为在第一步将第一个元素与其他元素交换，然后递归，在第二步将第二个元素与其他元素交换，依此类推。

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