Genera combinazioni ordinate per un attributo

Question

Sto cercando un modo per generare combinazioni di oggetti ordinati da un singolo attributo.Non credo che l'ordine lessicografico sia quello che sto cercando...Proverò a fare un esempio.Diciamo che ho un elenco di oggetti A,B,C,D con i valori degli attributi che voglio ordinare essendo 3,3,2,1.Questo dà oggetti A3, B3, C2, D1.Ora voglio generare combinazioni di 2 oggetti, ma devono essere ordinati in modo decrescente:

• A3B3
• A3 C2
• B3 C2
• A3D1
• B3D1
• C2D1

Generare tutte le combinazioni e ordinarle non è accettabile perché lo scenario del mondo reale prevede insiemi di grandi dimensioni e milioni di combinazioni.(set di 40, ordine di 8) e ho bisogno solo di combinazioni superiori a una determinata soglia.

In realtà ho bisogno del conteggio delle combinazioni sopra una soglia raggruppate in base alla somma di un dato attributo, ma penso che sia molto più difficile da fare, quindi mi accontenterei di sviluppare tutte le combinazioni sopra una soglia e di contarle.Se ciò è possibile.

EDIT - La mia domanda iniziale non era molto precisa...In realtà non ho bisogno di queste combinazioni ordinate, ho solo pensato che sarebbe stato utile isolare le combinazioni sopra una soglia.Per essere più precisi, nell'esempio sopra, dando una soglia pari a 5, sto cercando l'informazione che l'insieme dato produce 1 combinazione con una somma di 6 ( A3 B3 ) e 2 con una somma di 5 ( A3 C2, B3 C2).In realtà non ho bisogno delle combinazioni stesse.

Stavo esaminando il problema della somma dei sottoinsiemi, ma se ho capito correttamente data la soluzione dinamica ti fornirà solo informazioni se c'è una determinata somma o no, non il conteggio delle somme.

Grazie

Answer 1

In realtà, penso che tu Fare vogliono un ordine lessicografico, ma discendente anziché ascendente.Inoltre:

• Dalla tua descrizione non mi è chiaro che A, B,...D gioca qualsiasi ruolo nella tua risposta (tranne forse come contenitore per i valori).
• Penso che il tuo esempio di domanda sia semplicemente "Per ogni numero intero almeno 5, fino al massimo totale possibile di due valori, quante coppie distinte dell'insieme {3, 3, 2, 1} hanno somme di quel numero intero?"
• La parte interessante è il salvataggio anticipato, una volta che non è più possibile raggiungere una soluzione possibile (le somme rimanenti ottenibili sono troppo piccole).

In seguito pubblicherò il codice di esempio.

Ecco il codice di esempio che avevo promesso, con alcune osservazioni seguenti:

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

}

Osservazioni nella prefazione:

Questo utilizza una piccola classe di supporto chiamata Tally, che isola semplicemente la tabulazione (inclusa l'inizializzazione per chiavi mai viste prima).Lo metterò alla fine.

Per mantenerlo conciso, ho preso alcune scorciatoie che non sono una buona pratica per il codice "reale":

• Questo non verifica la presenza di un array di valori nulli, ecc.
• Presumo che l'array dei valori sia già ordinato in ordine decrescente, richiesto per la tecnica di salvataggio anticipato.(Un buon codice di produzione includerebbe l'ordinamento.)
• Inserisco i dati transitori nelle variabili di istanza invece di passarli come argomenti tra i metodi privati ​​che supportano count.Ciò rende questa classe non thread-safe.

Spiegazione:

Un'istanza di Combos viene creato con l'array (in ordine decrescente) di numeri interi da combinare.IL value l'array viene impostato una volta per istanza, ma più chiamate a count può essere realizzato con dimensioni e limiti di popolazione variabili.

IL count Il metodo attiva un attraversamento ricorsivo (per lo più) standard di combinazioni uniche di n numeri interi da values.IL limit argomento fornisce il limite inferiore delle somme di interesse.

IL countAt Il metodo esamina le combinazioni di numeri interi da values.IL left argomento è quanti numeri interi restano da comporre n numeri interi in una somma, start è la posizione in values da cui cercare, e sum è la somma parziale.

Il meccanismo di salvataggio anticipato si basa sull’informatica best, un array bidimensionale che specifica la "migliore" somma raggiungibile da un dato stato.Il valore in best[n][p] è la somma più grande di n valori che iniziano in posizione p dell'originale values.

La ricorsione di countAt tocca il fondo quando è stata accumulata la popolazione corretta;questo aggiunge la corrente sum (Di n valori) al tally.Se countAt non ha toccato il fondo, spazza il values dal start-ing posizione per incrementare il parziale corrente sum, fino a quando:

• rimangono abbastanza posizioni values per raggiungere la popolazione specificata, e
• IL best Il subtotale rimanente (più grande) è abbastanza grande da realizzare il limit.

Un esempio eseguito con i dati della tua domanda:

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

produce i risultati specificati:

found 2 sums of 5
found 1 sums of 6

Ecco il codice Tally:

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

ho scritto una classe per gestire funzioni comuni per lavorare con il coefficiente binomiale, che è il tipo di problema che il vostro problema rientra. Esso svolge i seguenti compiti:

1. Uscite tutti i K-indici in un bel formato per ogni k N scegliere di un file. K-indici possono essere sostituiti con stringhe più descrittive o lettere. Questo metodo rende risolvere questo tipo di problema piuttosto banale.

2. Converte i K-indici per il corretto indice di un voce nella tabella coefficiente binomiale ordinata. Questa tecnica è molto più veloce rispetto alle tecniche più vecchie pubblicati che si basano su iterazione. Lo fa utilizzando una proprietà matematica insita nel Triangolo di Pascal. La mia carta parla di questo. Credo di essere il primo a scoprire e pubblicare questa tecnica, ma potrei sbagliarmi.

3. Converte l'indice in una tabella coefficiente binomiale ordinato ai corrispondenti K-indici.

4. metodo Mark Dominus per calcolare il coefficiente binomiale, che è molto più in meno di probabilità di overflow e funziona con i numeri più grandi.

5. La classe è scritto in .NET C # e fornisce un modo per gestire gli oggetti relativi al problema (se presenti) utilizzando un elenco generico. Il costruttore di questa classe assume un valore booleano chiamato InitTable che quando vero creerà un elenco generico per contenere gli oggetti da gestire. Se questo valore è falso, allora non creare la tabella. La tabella non deve essere creato per eseguire i 4 metodi precedenti. metodi di accesso sono forniti per accedere alla tabella.

6. C'è una classe di test associata che mostra come utilizzare la classe e dei suoi metodi. E 'stato ampiamente testato con 2 casi e non ci sono bug noti.

Per leggere su questa classe e scaricare il codice, vedi Tablizing Il binomiale Coeffieicent .

Answer 3

Check out questa domanda in StackOverflow: Algoritmo per restituire tutte le combinazioni s

Inoltre ho appena usato un codice Java sotto per generare tutte le permutazioni, ma potrebbe essere facilmente utilizzato per generare unica combinazione di data di un indice.

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

Sono estremamente dispiaciuto (dopo tanti chiarimenti nei commenti) per dire che non riuscivo a trovare una soluzione efficace a questo problema. Ho provato per il passato ora senza risultati.

Il motivo (credo) è che questo problema è molto simile a problemi come il problema del commesso viaggiatore. Fino a meno che non si tenta tutte le combinazioni, non c'è modo di sapere quali attributi aggiungerà fino alla soglia.

Non sembra esserci alcun trucco intelligente in grado di risolvere questo tipo di problemi.

Ancora ci sono molte ottimizzazioni che si possono fare per il codice vero e proprio.

Prova l'ordinamento dei dati in base agli attributi. Si può essere in grado di evitare l'elaborazione di alcuni valori dalla lista quando si scopre che un valore superiore non può soddisfare la soglia (quindi tutti i valori più bassi possono essere eliminati).

Answer 5

Se stai usando C # c'è una discreta biblioteca generici qui . Si noti però che la generazione di alcuni permutazioni non è in ordine lessicografico

Answer 6

Ecco un approccio ricorsivo per count il numero di questi sottoinsiemi: Definiamo una funzione count(minIndex,numElements,minSum) che restituisce il numero di sottoinsiemi di numElements dimensioni cui somma è almeno minSum, contenente elementi con indici minIndex o maggiore .

Come nella dichiarazione problema, ordinare i nostri elementi in ordine decrescente, per esempio [3,3,2,1], e chiamare il primo indice di zero, e il numero totale di elementi N. Assumiamo tutti gli elementi sono non negativi. Per trovare tutte 2-sottoinsiemi la cui somma è almeno 5, che noi chiamiamo count(0,2,5).

Codice di esempio (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;
}

A proposito, ho eseguito quanto sopra con una serie di 40 elementi, e size-8 sottoinsiemi e costantemente tornato risultati in meno di un secondo.