Find the actual assignments of integers in arrays (permutations with a given order)

Question

I have a general problem finding a good algorithm to generate every possible assignment for some integers in different arrays.

Suppose I have n arrays and m numbers (I can have more arrays than numbers, more numbers than arrays, or as many arrays as numbers).

As an example, I have 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} 

So basically, I would like to find every possible combination to assign numbers to different arrays while preserving order. So, as in the example, 1 you always need to go in front of others and so on ...

I want to write an algorithm in C ++ / Qt to find all of these valid combinations.

Does anyone have an approach for me how to deal with this problem? How can I generate these permutations?

ADDITIONS

Unfortunately, I was not able to modify the excellent examples that you gave for the problem I am having right now, since the numbers I want to arrange in arrays are stored in an array (or QVector for me)

Can someone help me change the algorithm so that it gives me a possible real combination of numbers in QVector with QVector <QVector> so that I can do further calculations on each of them?

 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 

It would be great if someone 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 to make it work ...

Answer 1

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

These challenges ...

 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}, {}, {}, {} 

The approximate solution size (bucketsPerLine * NumberOfLines) dominates the execution time. For these tests, N is the length of the input array, and bucketsPerLine is also set to 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

It will be easy with recursion recursion. You have to keep track of which array you are filling and which number you are doing. Something like that:

 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 3

It smells like recursion. First, compute combinations to place m-1 in n arrays. Then you get n more solutions by placing the first number in any of the n arrays in these solutions.

Answer 4

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

In this case, it is divided into where 2 sections are located. There are 4 possible locations for 16 combinations, but that is not because you are deleting duplicates. A bit like domino tiles. You have 4 doubles here, and 12 singles are reduced to 6, so you have 10 combinations.

You can generate it by selecting the first, then creating the second as> = the first.

The first may be 0, 1, 2, or 3. 0 means that it appears before 1. 3 means that it appears after 3.

In your 10 decisions over sections are:

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

If you created an algorithmic order, you would probably have produced them 0 and 0, 0 and 1, 0 and 2, 0 and 3, 1 and 1, 1 and 2, 1 and 3, 2 and 2, 2 and 3, 3 and 3, although you can of course do them in reverse order.

In the above examples, look at the position of the commas and the number immediately to the left. If there are no numbers immediately to their left, then 0.