查找数组中整数的有效分配（给定顺序的排列）

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< 的每个可能的有效组合。 Q向量>这样我就可以对每一个进行进一步的计算？

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

Answer 2

这听起来像递归。首先计算将 m-1 放入 n 个数组的组合。然后，通过将第一个数字放入这些解决方案中的 n 个数组中的任意一个中，您可以得到 n 个以上的解决方案。

Answer 3

#include <vector>
#include <list>
#include <iostream>

class NestedCollection {
public:
    std::vector<std::list<int> > lists;

    NestedCollection(int n)
    : lists(n, std::list<int>())
    {};

    NestedCollection(const NestedCollection& other)
    : lists(other.lists)
    {};

    std::vector<NestedCollection> computeDistributions(int n, int m, int last_possible_index) {
        std::vector<NestedCollection> result;
        // iterate over all possible lists (invariant: last_possible_index >= i >= 0)
        // or skip if there is no number left to distribute (invariant: m>0)
        for(int i=last_possible_index; i>=0 && m>0 ; --i) {
            NestedCollection variation(*this);
            // insert the next number
            variation.lists[i].push_front(m);
            // recurse with all following numbers
            std::vector<NestedCollection> distributions = variation.computeDistributions(n, m-1, i);
            if(distributions.empty()) // we could also write if(m==1) - this guards the end of the recursion
                result.push_back(variation);
            else
                result.insert(result.end(), distributions.begin(), distributions.end() );
        }
        return result;
    };

    static std::vector<NestedCollection> findAllDistributions(int n, int m) {
        std::vector<NestedCollection> result;
        result = NestedCollection(n).computeDistributions(n, m, n-1);
        return result;
    };
};

int main() {
    int n=3, m=3;
    std::vector<NestedCollection> result = NestedCollection::findAllDistributions(n, m);
    for(std::vector<NestedCollection>::iterator it = result.begin(); it!=result.end(); ++it) {
        for(std::vector<std::list<int> >::iterator jt = it->lists.begin(); jt!=it->lists.end(); ++jt) {
            std::cout<<"{";
            for(std::list<int>::iterator kt = jt->begin(); kt!=jt->end(); ++kt) {
                std::cout<<*kt<<", ";
            }
            std::cout<<"} ";
        }
        std::cout<<std::endl;
    }
    return 0;
}

Answer 4

在这种情况下，它会分解到 2 个分区所在的位置。有 4 个可能的位置，因此将有 16 种组合，但这并不是因为您删除了“重复项”。有点像多米诺骨牌。这里有 4 个“双打”，12 个单打减少到 6 个，因此您有 10 种组合。

您可以选择第一个来生成它，然后将第二个生成为 >= 第一个。

第一个可以是 0、1、2 或 3。0 表示它出现在 1 之前。3 表示它出现在 3 之后。

在上面的 10 个解决方案中，分区位于：

1: 3 和 3
2：0和3
3：0和0
4：2和3
5：2和2
6：0和2
7：1和3
8：1和1
9：0和1
10: 1 和 2

如果您按照算法顺序生成，您可能会生成 0 和 0、0 和 1、0 和 2、0 和 3、1 和 1、1 和 2、1 和 3、2 和 2、2 和3、3 和 3，当然你也可以按照相反的顺序进行。

在上面的示例中，请查看逗号的位置以及紧邻其左侧的数字。如果紧邻其左边的数字没有，则为 0。

Answer 5

以下代码是用 C# 编写的。

class LineList<T> : List<T[][]> 
{
    public override string ToString()
    {
        var sb = new StringBuilder();
        sb.Append(Count).AppendLine(" lines:");
        foreach (var line in this)
        {
            if (line.Length > 0)
            {
                foreach (var bucket in line)
                {
                    sb.Append('{');
                    foreach (var item in bucket)
                    {
                        sb.Append(item).Append(',');
                    }
                    if (bucket.Length > 0)
                    {
                        sb.Length -= 1;
                    }
                    sb.Append("}, ");
                }
                sb.Length -= 2;
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }
}

class Permutor<T>
{
    public T[] Items { get; private set; }
    public bool ReuseBuckets { get; set; }
    private T[] emptyBucket_;
    private Dictionary<int, Dictionary<int, T[]>> buckets_;   // for memoization when ReuseBuckets=true
    public Permutor(T[] items)
    {
        ReuseBuckets = true;  // faster and uses less memory
        Items = items;
        emptyBucket_ = new T[0];
        buckets_ = new Dictionary<int, Dictionary<int, T[]>>();
    }
    private T[] GetBucket(int index, int size)
    {
        if (size == 0)
        {
            return emptyBucket_;
        }
        Dictionary<int, T[]> forIndex;
        if (!buckets_.TryGetValue(index, out forIndex))
        {
            forIndex = new Dictionary<int, T[]>();
            buckets_[index] = forIndex;
        }
        T[] bucket;
        if (!forIndex.TryGetValue(size, out bucket))
        {
            bucket = new T[size];
            Array.Copy(Items, index, bucket, 0, size);
            forIndex[size] = bucket;
        }
        return bucket;
    }
    public LineList<T> GetLines(int bucketsPerLine)
    {
        var lines = new LineList<T>();
        if (bucketsPerLine > 0)
        {
            AddLines(lines, bucketsPerLine, 0);
        }
        return lines;
    }
    private void AddLines(LineList<T> lines, int bucketAllotment, int taken)
    {
        var start = bucketAllotment == 1 ? Items.Length - taken : 0;
        var stop = Items.Length - taken;
        for (int nItemsInNextBucket = start; nItemsInNextBucket <= stop; nItemsInNextBucket++)
        {
            T[] nextBucket;
            if (ReuseBuckets)
            {
                nextBucket = GetBucket(taken, nItemsInNextBucket);
            }
            else
            {
                nextBucket = new T[nItemsInNextBucket];
                Array.Copy(Items, taken, nextBucket, 0, nItemsInNextBucket);
            }
            if (bucketAllotment > 1)
            {
                var subLines = new LineList<T>();
                AddLines(subLines, bucketAllotment - 1, taken + nItemsInNextBucket);
                foreach (var subLine in subLines)
                {
                    var line = new T[bucketAllotment][];
                    line[0] = nextBucket;
                    subLine.CopyTo(line, 1);
                    lines.Add(line);
                }
            }
            else
            {
                var line = new T[1][];
                line[0] = nextBucket;
                lines.Add(line);
            }
        }
    }

}

这些调用...

var permutor = new Permutor<int>(new[] { 1, 2, 3 });
for (int bucketsPerLine = 0; bucketsPerLine <= 4; bucketsPerLine++)
{
    Console.WriteLine(permutor.GetLines(bucketsPerLine));
}

生成此输出...

0 lines:

1 lines:
{1,2,3}

4 lines:
{}, {1,2,3}
{1}, {2,3}
{1,2}, {3}
{1,2,3}, {}

10 lines:
{}, {}, {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}, {}, {}

20 lines:
{}, {}, {}, {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}, {}, {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}, {}, {}, {}

解决方案的大致大小 (bucketsPerLine * NumberOfLines) 主导执行时间。对于这些测试，N 是输入数组的长度，bucketsPerLine 也设置为 N。

N=10, solutionSize=923780, elapsedSec=0.4, solutionSize/elapsedMS=2286
N=11, solutionSize=3879876, elapsedSec=2.1, solutionSize/elapsedMS=1835
N=12, solutionSize=16224936, elapsedSec=10.0, solutionSize/elapsedMS=1627
N=13, solutionSize=67603900, elapsedSec=47.9, solutionSize/elapsedMS=1411