Generieren Kombinationen durch ein Attribut bestellt

Question

Ich bin auf der Suche nach einer Möglichkeit, Kombinationen von Objekten durch ein einziges Attribut bestellt zu erzeugen. Ich glaube nicht, lexikographische Ordnung ist das, was ich suche ... Ich werde versuchen, ein Beispiel zu geben. Lassen Sie uns sagen, ich habe eine Liste von Objekten A, B, C, D mit den Attributwerten I, indem sie 3,3,2,1 bestellen möchten. Dies ergibt A3, B3, C2, D1 Objekte. Jetzt möchte ich Kombinationen von zwei Objekten erzeugen, aber sie müssen in absteigender Weise bestellt werden:

• A3 B3
• A3 C2
• B3 C2
• A3 D1
• B3 D1
• C2 D1

Die Erzeugung alle Kombinationen und sie Sortierung ist nicht akzeptabel, weil die reale Welt Szenario große Mengen und Millionen von Kombinationen umfasst. (Satz von 40, um von 8), und ich brauche nur Kombinationen, die über der bestimmte Schwelle.

Eigentlich brauche ich von Kombinationen über einem Schwellenwert durch eine Summe eines bestimmten Attribut gruppiert zählen, aber ich denke, dass es viel schwieriger ist, zu tun - so würde ich für die Entwicklung alle Kombinationen über einer Schwelle absetzen und sie zu zählen. Wenn das überhaupt möglich.

EDIT - Meine ursprüngliche Frage war nicht sehr genau ... Ich brauche nicht wirklich diese Kombinationen bestellt, dachte nur, es würde helfen, Kombinationen über einem Schwellenwert zu isolieren. Um genauer zu sein, in dem obigen Beispiel eine Schwelle von 5 zu geben, ich bin für eine Information, dass die gegebene Menge produziert 1 Kombination mit einer Summe aus 6 (A3 B3) und 2 mit einer Summe von 5 (A3 C2, B3 C2). Ich weiß nicht wirklich brauchen, um die Kombinationen selbst.

Ich war auf der Suche in Subset-Sum Problem, aber wenn ich mich recht dynamische Lösung besser verständlich wird es Ihnen nur Informationen gibt es eine bestimmte Summe oder nein, nicht die Summen rechnen.

Danke

Answer 1

Tatsächlich, ich glaube, Sie Sie wollen lexicographic Ordnung, sondern absteigend statt steigend. Darüber hinaus:

• Es ist mir nicht klar, aus Ihrer Beschreibung, die A, B, ... D eine Rolle (außer vielleicht als Behälter für die Werte) in Ihrer Antwort spielen.
• denke ich Ihre Frage Beispiel ist einfach „Für jede ganze Zahl von mindestens 5 bis zum maximal möglichen insgesamt zwei Werten, wie viele verschiedenen Paare aus der Menge {3, 3, 2, 1} haben Summen dieser ganze Zahl? „
• Der interessante Teil ist die frühe bailout, sobald keine mögliche Lösung (verbleibende erreichbare Summen sind zu klein) erreicht werden kann.

Ich werde Beispielcode schreiben später.

Hier ist der Beispielcode ich versprochen, mit einigen Bemerkungen folgt vor:

public class Combos {

    /* permanent state for instance */
    private int values[];
    private int length;

    /* transient state during single "count" computation */
    private int n;
    private int limit;
    private Tally<Integer> tally;
    private int best[][];  // used for early-bail-out

    private void initializeForCount(int n, int limit) {
        this.n = n;
        this.limit = limit;
        best = new int[n+1][length+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length - i; ++j) {
                best[i][j] = values[j] + best[i-1][j+1];
            }
        }
    }

    private void countAt(int left, int start, int sum) {
        if (left == 0) {
            tally.inc(sum);
        } else {
            for (
                int i = start;
                i <= length - left
                && limit <= sum + best[left][i];  // bail-out-check
                ++i
            ) {
                countAt(left - 1, i + 1, sum + values[i]);
            }
        }
    }

    public Tally<Integer> count(int n, int limit) {
        tally = new Tally<Integer>();
        if (n <= length) {
            initializeForCount(n, limit);
            countAt(n, 0, 0);
        }
        return tally;
    }

    public Combos(int[] values) {
        this.values = values;
        this.length = values.length;
    }

}

Vorwort Bemerkungen:

Dieses verwendet einen kleinen Helfer Klasse namens Tally, die nur die tabellarische Isolaten (einschließlich Initialisierung für nie dagewesene Tasten). Ich werde es am Ende setzen.

Diese prägnanten zu halten, habe ich einige Abkürzungen genommen, die nicht gute Praxis für die „echten“ Code sind:

• Diese sucht nicht nach einem Nullwert Array, etc.
• Ich gehe davon aus, dass der Wert Array bereits in absteigender Reihenfolge sortiert wird, die für die frühen-bail-out-Technik. (Guter Produktions Code würde die Sortierung enthalten.)
• Ich habe transiente Daten in Instanzvariablen, anstatt sie als Argumente unter den privaten Methoden vorbei, die count unterstützen. Das macht diese Klasse nicht-Thread-sicher.

Erklärung:

Eine Instanz Combos zusammen mit dem (absteigend geordnet) Array von ganzen Zahlen zu kombinieren erstellt. Die value Array wird einmal pro Instanz eingerichtet, aber mehrere Aufrufe count können mit unterschiedlichen Populationsgrößen und Grenzen gemacht werden.

Die count Methode löst einen (meist) Standard rekursive Traversal von einzigartigen Kombinationen von n ganzen Zahlen von values. Das limit Argument gibt die untere Grenze auf Summen von Interesse.

Die countAt Methode untersucht Kombinationen von Zahlen von values. Das left Argument ist, wie viele Zahlen bleiben n ganze Zahlen in einer Summe zu bilden, start ist die Position, in values, von dem suchen, und sum ist die Teilsumme.

Der frühe bail-out-Mechanismus auf der Berechnung best basiert, ein zweidimensionales Array, das die „beste“ Summe erreichbar von einem bestimmten Zustand angibt. Der Wert in best[n][p] ist die größte Summe von n Werten beginnend in Position p des ursprünglichen values.

Die Rekursion von countAt Böden aus, wenn die richtige Bevölkerung angesammelt hat; Dies fügt den aktuellen sum (von n Werte) an den tally. Wenn countAt nicht die Talsohle erreicht hat, er fegt den values vom start-ing Position mit dem aktuellen Teil sum zu erhöhen, solange:

• genug Positionen bleiben in values die angegebene Bevölkerung zu erreichen, und
• der best (größte) Wert Ihrer verbleibenden ist groß genug, um die limit zu machen.

Ein Probelauf mit Ihrer Frage Daten:

    int[] values = {3, 3, 2, 1};
    Combos mine = new Combos(values);
    Tally<Integer> tally = mine.count(2, 5);
    for (int i = 5; i < 9; ++i) {
        int n = tally.get(i);
        if (0 < n) {
            System.out.println("found " + tally.get(i) + " sums of " + i);
        }
    }

erzeugt die Ergebnisse, die Sie angegeben:

found 2 sums of 5
found 1 sums of 6

Hier ist der Tally-Code:

public static class Tally<T> {
    private Map<T,Integer> tally = new HashMap<T,Integer>();
    public Tally() {/* nothing */}
    public void inc(T key) {
        Integer value = tally.get(key);
        if (value == null) {
            value = Integer.valueOf(0);
        }
        tally.put(key, (value + 1));
    }
    public int get(T key) {
        Integer result = tally.get(key);
        return result == null ? 0 : result;
    }
    public Collection<T> keys() {
        return tally.keySet();
    }
}

Answer 2

Ich habe eine Klasse geschrieben gemeinsame Funktionen zu handhaben, um mit dem Binomialkoeffizienten arbeiten, die die Art des Problems ist, dass Ihr Problem unter fällt. Es führt die folgenden Aufgaben:

1. Gibt alle K-Indizes in einem praktischen Format für jede N K in eine Datei wählen. Der K-Indizes kann mit mehr beschreibenden Strings oder Buchstaben ersetzt werden. Dieses Verfahren macht diese Art von Problem ganz trivial zu lösen.

2. Wandelt die K-Indizes in den richtigen Index eines Eintrags in der sortierten Binomialkoeffizient Tabelle. Diese Technik ist viel schneller als ältere veröffentlichten Techniken, die auf Iteration verlassen. Es tut dies durch eine mathematische Eigenschaft inhärent Pascals Dreieck verwenden. Mein Papier spricht darüber. Ich glaube, ich bin die erste zu entdecken und diese Technik zu veröffentlichen, aber ich könnte falsch sein.

3. Wandelt den Index in einer sortierten Binomialkoeffizient Tabelle zu den entsprechenden K-Indizes.

4. Mark Dominus Verfahren den Binomialkoeffizient zu berechnen, die viel weniger wahrscheinlich zu überlaufen und arbeitet mit einer größeren Anzahl.

5. Die Klasse ist in .NET C # geschrieben und bietet eine Möglichkeit, die Objekte für das Problem (falls vorhanden) unter Verwendung einer generische Liste mit Bezug zu verwalten. Der Konstruktor dieser Klasse nimmt einen Bool-Wert namens InitTable, dass, wenn true, um eine generische Liste erstellen wird, die Objekte zu halten verwaltet werden. Wenn dieser Wert falsch ist, dann wird es nicht in die Tabelle erstellen. Die Tabelle muss nicht in Reihenfolge erstellt werden, um die obigen Verfahren 4 durchzuführen. Accessormethoden sind vorgesehen, um die Tabelle zugreifen.

6. Es gibt eine zugehörige Testklasse, die zeigt, wie die Klasse und ihre Methoden verwenden. Es wurde mit 2 Fällen ausgiebig getestet und es gibt keine bekannten Fehler.

über diese Klasse zu lesen und den Code herunterzuladen, finden Sie unter Tablizing Binomialmodelle Coeffieicent .

Answer 3

diese Frage in Stackoverflow Check out: Algorithm Rückkehr aller Kombination s

Ich habe auch nur den Java-Code unter alle Permutationen zu erzeugen, aber es leicht verwendet werden könnten einzigartige Kombination der gegebenen einen Index zu erzeugen.

public static <E> E[] permutation(E[] s, int num) {//s is the input elements array and num is the number which represents the permutation

    int factorial = 1;

    for(int i = 2; i < s.length; i++)
        factorial *= i;//calculates the factorial of (s.length - 1)

    if (num/s.length >= factorial)// Optional. if the number is not in the range of [0, s.length! - 1] 
        return null;

    for(int i = 0; i < s.length - 1; i++){//go over the array

        int tempi = (num / factorial) % (s.length - i);//calculates the next cell from the cells left (the cells in the range [i, s.length - 1])
        E temp = s[i + tempi];//Temporarily saves the value of the cell needed to add to the permutation this time 

        for(int j = i + tempi; j > i; j--)//shift all elements to "cover" the "missing" cell
            s[j] = s[j-1];

        s[i] = temp;//put the chosen cell in the correct spot

        factorial /= (s.length - (i + 1));//updates the factorial

    }

    return s;
}

Answer 4

Ich bin sehr traurig (nach all den Erklärungen in den Kommentaren) zu sagen, dass ich nicht eine effiziente Lösung für dieses Problem gefunden. Ich habe versucht, für die vergangene Stunde ohne Ergebnisse.

Der Grund (glaube ich) ist, dass dieses Problem zu Problemen wie das Reiseproblem sehr ähnlich ist. Bis es sei denn, Sie alle Kombinationen versuchen, gibt es keine Möglichkeit zu wissen, welche bis zu der Schwelle fügt Attribute.

Es scheint kein cleverer Trick zu sein, die diese Klasse von Problemen lösen können.

Dennoch gibt es viele Optimierungen, die Sie mit dem eigentlichen Code tun können.

Versuchen Sie, die Datensortierung die Attribute nach. Sie können die Bearbeitung einige Werte aus der Liste vermeiden können, wenn Sie, dass ein höherer Wert finden nicht den Schwellenwert erfüllen kann (so dass alle niedrigere Werte eliminiert werden können).

Answer 5

Wenn Sie mit C # gibt es eine ziemlich gute Generika Bibliothek hier . anzumerken, dass die Erzeugung von einigen Permutationen ist nicht in lexikographischer Ordnung

Answer 6

Hier ist eine rekursive Ansatz zu count die Anzahl dieser Untergruppen: Wir definieren eine Funktion count(minIndex,numElements,minSum), die die Anzahl von Teilmengen von Größe numElements, deren Summe zurückgibt, ist zumindest minSum, die Elemente enthält, mit Indizes minIndex oder größer .

Wie in der Problemstellung, sortieren wir unsere Elemente in absteigender Reihenfolge, z.B. [3,3,2,1], und rufen Sie den ersten Index Null, und die Gesamtzahl der Elemente N. sind Wir übernehmen alle Elemente nichtnegativ. Für alle 2-Subsets, deren Summe mindestens 5, nennen wir count(0,2,5).

Beispielcode (Java):

int count(int minIndex, int numElements, int minSum)
{
    int total = 0;

    if (numElements == 1)
    {
        // just count number of elements >= minSum
        for (int i = minIndex; i <= N-1; i++)
            if (a[i] >= minSum) total++; else break;
    }
    else
    {
        if (minSum <= 0)
        {
            // any subset will do (n-choose-k of them)
            if (numElements <= (N-minIndex))
                total = nchoosek(N-minIndex, numElements);
        }
        else
        {
            // add element a[i] to the set, and then consider the count
            // for all elements to its right
            for (int i = minIndex; i <= (N-numElements); i++)
                total += count(i+1, numElements-1, minSum-a[i]);
        }
    }

    return total;
}

Btw, ich habe das oben mit einer Reihe von 40 Elementen läuft und Größe-8-Untergruppen und bekamen durchweg Ergebnisse in weniger zurück als eine Sekunde.