查找数组中的整数有效的分配（排列与给定顺序） [英] Find valid assignments of integers in arrays (permutations with given order)
问题描述
我有一个普遍的问题找到一个好的算法，用于产生在不同的阵列一些整数每一个可能的任务。
I am having a general problem finding a good algorithm for generating each possible assignment for some integers in different arrays.
可以说我有n个阵列和M号（我可以有比数字更数组，数组比更号码或尽可能多的数组作为数字）。
Lets say I have n arrays and m numbers (I can have more arrays than numbers, more numbers than arrays or as much arrays as numbers).
作为一个例子，我有数字1,2,3和三个数组：
As an example I have the numbers 1,2,3 and three arrays:
{}，{}，{}
现在我想找到这些解决方案：
Now I would like to find each of these solutions:
{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总是需要落入他人面前等等...
So basically I would like to find each possible combination to assign the numbers to the different arrays with keeping the order. So as in the example the 1 always needs to come before the others and so on...
我想用C ++ / Qt的一个算法来找到所有这些有效组合。
I want to write an algorithm in C++/Qt to find all these valid combinations.
是否有人对如何处理这个问题，我的做法？我怎么会产生这种排列？
Does anybody have an approach for me on how to handle this problem? How would I generate these permutations?
ADDITIONS
可惜我没改变你给的问题，我现在有很好的例子，因为我想安排在阵列中的号码存储在一个阵列（或对我来说是QVector）
Unfortunately I didn't manage to change the great examples you gave for the problem I have now, since the numbers that I want to arrange in the arrays are stored in an array (or for me a QVector)
任何人可以帮助我改变算法，使得它给我的号码在QVector到QVector＆LT每一个可能的有效组合; QVector>这样我可以在每一个做进一步的计算？
Can anybody help me change the algorithm so that it gives me each possible valid combination of the numbers in the QVector to the QVector< QVector > so that I can do further computations on each one?
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
将是真正伟大的，如果有人能为我提供一个简单的实现，它的工作原理或如何得到它的提示...我只是无法改变已经提供了这样它的工作原理code ...
Would be really great if anyone could provide me with a simple implementation that works or tips on how to get it... I just couldn't change the code that was already provided so that it works...
推荐答案
以下code是用C＃。
The following code is written in 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));
}
产生这个输出...
generate this output...
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，以及
The approximate size of the solution (bucketsPerLine * NumberOfLines) dominates the execution time. For these tests, N is the length of the input array and the bucketsPerLine is set to N as well.
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
这篇关于查找数组中的整数有效的分配（排列与给定顺序）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
