Finde gültige Zuweisungen von ganzen Zahlen in Arrays (Permutationen mit gegebener Reihenfolge)

Question

Ich habe ein allgemeines Problem, einen guten Algorithmus zu finden, um jede mögliche Zuweisung für einige Ganzzahlen in verschiedenen Reihen zu erzeugen.

Sagen wir, ich habe n Arrays und m Zahlen (ich kann mehr Arrays als Zahlen haben, mehr Zahlen als Arrays oder so viele Arrays wie Zahlen).

Als Beispiel habe ich die Zahlen 1,2,3 und drei Arrays:

{} {} {}

Jetzt würde ich jede dieser Lösungen finden wie:

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

Also grundsätzlich möchte ich jede mögliche Kombination finden, um die Nummern den verschiedenen Arrays unter Beibehaltung der Reihenfolge zuzuweisen. Also wie im Beispiel muss die 1 immer vor die anderen kommen und so weiter ...

Ich möchte einen Algorithmus in C++/Qt schreiben, um alle diese gültigen Kombinationen zu finden.

Hat jemand einen Ansatz für mich, wie mit diesem Problem umzugehen? Wie würde ich diese Permutationen erzeugen?

ADDITIONS

Leider habe ich nicht gelingt, die großen Beispiele ändern Sie für das Problem habe ich jetzt habe, da die Zahlen, die ich in den Arrays anordnen möchten in einem Array gespeichert sind (oder für mir ein QVector)

Kann jemand mir helfen, den Algorithmus zu ändern, damit er mir jede mögliche gültige Kombination der Zahlen im QVector zum QVector gibt < QVector> damit ich weitere Berechnungen auf jedem machen kann?

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 

Wäre echt toll, wenn mir jemand mit einer einfachen Implementierung zur Verfügung stellen könnte, die auf Arbeiten oder Tipps, wie es zu bekommen ... Ich konnte einfach nicht den Code ändern, der bereits so vorgesehen war, dass es funktioniert ..

Answer 1

Der folgende Code ist in C# geschrieben.

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

} 

Diese Anrufe ...

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

diesen Ausgang erzeugen ...

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

Die ungefähre Größe der Lösung (bucketsPerLine * NumberOfLines) dominiert die Ausführungszeit. Für diese Tests ist N die Länge des Eingabearrays und die BucketsPerLine ist ebenfalls auf N festgelegt.

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

Das riecht nach Rekursion. Berechnen Sie zuerst die Kombinationen, um m-1 in n Arrays zu setzen. Dann erhalten Sie weitere Lösungen, indem Sie die erste Zahl in eines der n Arrays in diesen Lösungen setzen.

Answer 3

Dies ist einfach mit Backtracking-Rekursion. Sie sollten verfolgen, welches Array Sie ausfüllen und welche Nummer Sie haben. Etwas wie das:

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

Es bricht in diesem Fall zu, wo die 2 Partitionen sind. Es gibt 4 mögliche Standorte, also wären es 16 Kombinationen, aber das liegt nicht daran, dass Duplikate entfernt werden. Ein bisschen wie Dominosteine. Sie haben hier 4 "Doppel" und die 12 Singles reduzieren sich auf 6, so dass Sie 10 Kombinationen haben.

Sie können generieren, indem Sie die erste auswählen und dann die zweite als> = die erste generieren.

Die erste kann 0, 1, 2 oder 3 sein. 0 bedeutet, dass es vor der 1. 3 erscheint, es erscheint nach der 3.

In Ihren 10 Lösungen oberhalb den Trennwänden sind bei:

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

Wenn Sie in algorithmischer Reihenfolge erzeugt würden Sie wahrscheinlich produzieren sie 0 und 0, 0 und 1, 0 und 2, 0 und 3, 1 und 1, 1 und 2, 1 und 3, 2 und 2, 2 und 3, 3 und 3, obwohl Sie von cour se tun sie in umgekehrter Reihenfolge.

In den obigen Beispielen sehen Sie sich die Positionen der Kommas und die Zahl unmittelbar links von ihnen an. Wenn sich links von ihnen keine Nummern befinden, ist es 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; 
}