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

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中编写一个算法来查找所有这些有效组合。

有没有人有我的方法来处理这个问题？我将如何产生这些排列？

ADDITIONS

可惜我没改，你给了我现在的问题很好的例子，因为我想在阵列排列的号码存储在一个阵列（或我是一个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

以下代码是用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 

Answer 2

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

Answer 3

这将很容易与回溯递归。你应该跟踪你正在填写哪个数组，以及你正在填写哪个数字。类似的东西：

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

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