Kartesisches Produkt implementieren, so dass Iterationen übersprungen werden können.

Question

Ich möchte eine Funktion implementieren, die das kartesische Produkt der Menge zurückgibt. Zum Beispiel

input: {a, b}, 2 
output: 
aa 
ab 
bb 
ba 

input: {a, b}, 3 
aaa 
aab 
aba 
baa 
bab 
bba 
bbb 

jedoch der einzige Weg, ich umsetzen kann es erstens tut cartesion Produkt für 2 Sätze („ab“, „ab), dann aus dem Ausgang des Satzes, den gleichen Satz hinzuzufügen. Hier ist Pseudo -Code:

function product(A, B): 
    result = [] 
    for i in A: 
     for j in B: 
      result.append([i,j]) 
    return result 
function product1(chars, count): 
    result = product(chars, chars) 
    for i in range(2, count): 
     result = product(result, chars) 
    return result 

Was ich will, ist direkt mit dem letzten Satz zu starten Berechnung, ohne bevor es alle Sätze Computing ist dies möglich, auch eine Lösung, die mir ähnliches Ergebnis geben wird, aber es ist nicht. kartesisches Produkt ist akzeptabel Ich habe kein Problem beim Lesen der meisten allgemeinen Programmiersprachen, also wenn Sie Code eingeben müssen, können Sie es in jeder Sprache tun, die Sie fühlte sich wohl mit.

Answer 1

Hier ist ein rekursiver Algorithmus, der S^n erstellt, ohne S^(n-1) "first" zu erstellen. Stellen Sie sich einen unendlichen k-ary Baum mit | S | vor = k. Beschriften Sie mit den Elementen von S jede der Kanten, die einen Elternteil mit seinen k Kindern verbinden. Ein Element von S^m kann als irgendein Pfad der Länge m von der Wurzel betrachtet werden. Die Menge S^m ist in dieser Denkweise die Menge aller solcher Wege. Nun ist das Problem, S^n zu finden, ein Problem beim Aufzählen aller Pfade der Länge n - und wir können einen Pfad benennen, indem wir die Reihenfolge der Kantenbeschriftungen vom Anfang bis zum Ende betrachten. Wir wollen S^n direkt generieren, ohne zuerst alle von S^(n-1) zu berechnen, daher erscheint eine Tiefensuche, die so modifiziert wurde, dass alle Knoten in der Tiefe n gefunden werden, angemessen. Dies ist im Wesentlichen, wie der folgende Algorithmus arbeitet:

// collection to hold generated output 
members = [] 

// recursive function to explore product space 
Products(set[1...n], length, current[1...m]) 

    // if the product we're working on is of the 
    // desired length then record it and return 
    if m = length then 
     members.append(current) 
     return 

    // otherwise we add each possible value to the end 
    // and generate all products of the desired length 
    // with the new vector as a prefix 
    for i = 1 to n do 
     current.addLast(set[i]) 
     Products(set, length, current) 
     currents.removeLast() 

// reset the result collection and request the set be generated 
members = [] 
Products([a, b], 3, []) 

nun eine Breiten ersten Ansatz ist nicht weniger effizient als ein Tiefe-erste, und wenn man darüber nachdenkt, würde von genau das nicht anders sein, was du bist schon. In der Tat, und der Ansatz, der S^erzeugt, muss notwendigerweise S^(n-1) mindestens einmal erzeugen, da dies in einer Lösung für S^n gefunden werden kann.