c++ - 在数组中查找整数的有效分配(具有给定顺序的排列)

Question

我在寻找一个好的算法来为不同数组中的某些整数生成每个可能的赋值时遇到一个普遍问题。

假设我有 n 个数组和 m 个数字(我可以有比数字更多的数组，比数组更多的数字或与数字一样多的数组)。

例如，我有数字 1、2、3 和三个数组:

{ }、{ }、{ }

现在我想找到以下每个解决方案:

{1,2,3}, { }, { }
{ }, {1,2,3}, { }
{ }, { }, {1,2,3}
{1,2}, {3}, { }
{1,2}, { }, {3}
{ }, {1,2}, {3}
{1}, {2,3}, { }
{1}, { }, {2,3}
{ }, {1}, {2,3}
{1}, {2}, {3}

所以基本上我想找到每个可能的组合，以将数字分配给不同的数组并保持顺序。所以在这个例子中，1 总是需要排在其他人之前，依此类推......

我想用 C++/Qt 编写一个算法来找到所有这些有效组合。

有没有人能告诉我如何处理这个问题？我将如何生成这些排列？

添加

不幸的是，我没有设法改变你为我现在遇到的问题给出的很好的例子，因为我想排列在数组中的数字存储在一个数组中(或者对我来说是一个 QVector)

任何人都可以帮助我更改算法，以便它为我提供 QVector 和 QVector< QVector > 中数字的每个可能有效组合，以便我可以对每个组合进行进一步计算吗？

QVector<int> line; // contains the numbers: like {7,3,6,2,1}
QVector< QVector<int> > buckets; // empty buckets for the numbers { {}, {}, {} }

QList< QVector< QVector<int> > > result; // List of all possible results

如果有人能为我提供一个简单的可行的实现或如何获得它的提示，那就太好了......我只是无法更改已经提供的代码以使其工作......

Answer 1

回溯递归很容易做到这一点。您应该跟踪您正在填充的阵列以及您达到的数量。类似的东西:

void gen(int arrayN, int number)
{
   if (number == MAX_NUMBER + 1) //We have a solution
   {
        printSolution();
        return;
   }

   if (arrayN == MAX_ARRAYS + 1) //No solution
       return;

   gen(arrayN + 1, number); //Skip to next array

   for (int i = number; i <= MAX_NUMBER; i++)
   {
       //Save at this line the numbers into an array for the solution
       gen(arrayN + 1, i + 1); //Used the numbers from "number" to "i" inclusive
   }
}

gen(0, 1);