如何迭代属于同一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]
    }
}

I如果我想遍历三个元素的所有配置，我只需为 $ c>迭代：

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

回答
解决方案就是这个功能：

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:

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

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屋！