n-esima combinazione arbitraria di un set grande

Question

Dire che ho un numero di numeri da [0, ....., 499]. Le combinazioni vengono attualmente generate in sequenza utilizzando C++ std::next_permutation. Per riferimento, la dimensione di ciascuna tupla che sto ritirando è 3, quindi restituisco risultati sequenziali come [0,1,2], [0,1,3], [0,1,4], ... [497,498,499].

Ora, voglio parallelizzare il codice in cui si trova, quindi una generazione sequenziale di queste combinazioni non funzionerà più. Esistono algoritmi esistenti per calcolare la combinazione ith di 3 da 500 numeri?

Voglio assicurarmi che ogni thread, indipendentemente dalle iterazioni del ciclo che ottiene, possa calcolare una combinazione autonoma basata su iterazione con i. Quindi, se desidero la combinazione per i=38 nella discussione 1, è possibile calcolare [1,2,5] e calcolare contemporaneamente i=0 nella discussione 2 come [0,1,2].

EDIT seguito affermazione è irrilevante, mi sono confuso

ho guardato algoritmi che utilizzano fattoriali per restringere ogni singolo elemento da sinistra a destra, ma non posso usare questi come 500! sicuro non si adatterà alla memoria. Eventuali suggerimenti?

Answer 1

Ecco il mio colpo:

int k = 527; //The kth combination is calculated 
int N=500; //Number of Elements you have 
int a=0,b=1,c=2; //a,b,c are the numbers you get out 

while(k >= (N-a-1)*(N-a-2)/2){ 
    k -= (N-a-1)*(N-a-2)/2; 
    a++; 
} 
b= a+1; 
while(k >= N-1-b){ 
    k -= N-1-b; 
    b++; 
} 

c = b+1+k; 


cout << "["<<a<<","<<b<<","<<c<<"]"<<endl; //The result 

avuto questo pensiero di quante combinazioni ci sono fino a quando viene aumentato il numero successivo. Tuttavia funziona solo per tre elementi. Non posso garantire che sia corretto. Sarebbe bello se lo confrontassi con i tuoi risultati e dare un feedback.

Answer 2

È possibile descrivere una particolare selezione di 3 su 500 oggetti come una tripla (i, j, k), dove i è un numero da 0 a 499 Euro (l'indice del primo numero), j varia da 0 a 498 (l'indice in secondo luogo, ignorando il numero precedente) e gli intervalli k da 0 a 497 (indice dell'ultimo, ignorando entrambi i numeri selezionati in precedenza). Dato che, in realtà è abbastanza facile enumerare tutte le possibili selezioni: a partire da (0,0,0), incrementare k fino a raggiungere il valore massimo, quindi incrementare j e reimpostare k su 0 e così via, fino a quando j raggiunge il valore massimo, quindi on, fino a j ottiene il proprio valore massimo; quindi incrementare i e ripristinare entrambi j e k e continuare.

Se questa descrizione suona familiare, è perché è esattamente nello stesso modo che incrementare un numero in base 10 opere, tranne che la base è molto più funky, e in effetti la base varia da una cifra all'altra. È possibile utilizzare questa intuizione per implementare una versione molto compatta dell'idea: per ogni intero n da 0 a 500 * 499 * 498, è possibile ottenere:

struct { 
    int i, j, k; 
} triple; 

triple AsTriple(int n) { 
    triple result; 
    result.k = n % 498; 
    n = n/498; 
    result.j = n % 499; 
    n = n/499; 
    result.i = n % 500; // unnecessary, any legal n will already be between 0 and 499 
    return result; 
} 

void PrintSelections(triple t) { 
    int i, j, k; 
    i = t.i; 
    j = t.j + (i <= j ? 1 : 0); 
    k = t.k + (i <= k ? 1 : 0) + (j <= k ? 1 : 0); 
    std::cout << "[" << i << "," << j << "," << k << "]" << std::endl; 
} 

void PrintRange(int start, int end) { 
    for (int i = start; i < end; ++i) { 
    PrintSelections(AsTriple(i)); 
    } 
} 

Ora per frammento, si può semplicemente prendere i numeri da Da 0 a 500 * 499 * 498, dividerli in intervalli secondari nel modo che preferisci e fare in modo che ogni frammento calcoli la permutazione per ogni valore nel suo subrange.

Questo trucco è molto utile per qualsiasi problema in cui è necessario enumerare sottoinsiemi.

Answer 3

Se stai cercando un modo per ottenere l'indice lessicografico o il rango di una combinazione unica invece di una permutazione, allora il tuo problema rientra nel coefficiente binomiale. Il coefficiente binomiale gestisce i problemi di scelta di combinazioni uniche in gruppi di K con un totale di N elementi.

Ho scritto una classe in C# per gestire le funzioni comuni per lavorare con il coefficiente binomiale.Esso svolge i seguenti compiti:

1. Uscite tutti i K-indici in un bel formato per qualsiasi N scegliere K in un file. Gli indici K possono essere sostituiti con stringhe o lettere più descrittive.

2. Converte gli indici K nell'indice lessicografico corretto o nella classificazione di una voce nella tabella del coefficiente binomiale ordinato. Questa tecnica è molto più veloce delle vecchie tecniche pubblicate che fanno affidamento sull'iterazione. Lo fa usando una proprietà matematica inerente al triangolo di Pascal ed è molto efficiente rispetto all'iterazione sul set.

3. Converte l'indice in una tabella di coefficiente binomiale ordinata negli indici K corrispondenti. Credo che sia anche più veloce delle vecchie soluzioni iterative.

4. Utilizza il metodo Mark Dominus per calcolare il coefficiente binomiale, che è molto meno probabile che si verifichi un overflow e funzioni con numeri più grandi.

5. La classe è scritta in .NET C# e offre un modo per gestire gli oggetti correlati al problema (se presenti) utilizzando un elenco generico. Il costruttore di questa classe prende un valore bool chiamato InitTable che quando true creerà un elenco generico per contenere gli oggetti da gestire. Se questo valore è falso, non creerà la tabella. Non è necessario creare la tabella per utilizzare i 4 metodi precedenti. I metodi di accesso sono forniti per accedere alla tabella.

6. Esiste una classe di test associata che mostra come utilizzare la classe e i suoi metodi. È stato ampiamente testato con 2 casi e non ci sono bug noti.

Per leggere su questa classe e scaricare il codice, vedere Tablizing The Binomial Coeffieicent.

Il codice testato seguente sarà Sperimenta ogni combinazioni uniche:

public void Test10Choose5() 
{ 
    String S; 
    int Loop; 
    int N = 500; // Total number of elements in the set. 
    int K = 3; // Total number of elements in each group. 
    // Create the bin coeff object required to get all 
    // the combos for this N choose K combination. 
    BinCoeff<int> BC = new BinCoeff<int>(N, K, false); 
    int NumCombos = BinCoeff<int>.GetBinCoeff(N, K); 
    // The Kindexes array specifies the indexes for a lexigraphic element. 
    int[] KIndexes = new int[K]; 
    StringBuilder SB = new StringBuilder(); 
    // Loop thru all the combinations for this N choose K case. 
    for (int Combo = 0; Combo < NumCombos; Combo++) 
    { 
     // Get the k-indexes for this combination. 
     BC.GetKIndexes(Combo, KIndexes); 
     // Verify that the Kindexes returned can be used to retrive the 
     // rank or lexigraphic order of the KIndexes in the table. 
     int Val = BC.GetIndex(true, KIndexes); 
     if (Val != Combo) 
     { 
     S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString(); 
     Console.WriteLine(S); 
     } 
     SB.Remove(0, SB.Length); 
     for (Loop = 0; Loop < K; Loop++) 
     { 
     SB.Append(KIndexes[Loop].ToString()); 
     if (Loop < K - 1) 
      SB.Append(" "); 
     } 
     S = "KIndexes = " + SB.ToString(); 
     Console.WriteLine(S); 
    } 
} 

si dovrebbe essere in grado di porto questa classe nel corso abbastanza facilmente in C++. Probabilmente non dovrai eseguire il porting sulla parte generica della classe per raggiungere i tuoi obiettivi. Il tuo test case di 500 sceglie 3 rese 20.708.500 combinazioni uniche, che si adatteranno in un int byte da 4 byte. Se 500 scegli 3 è semplicemente un caso esemplificativo e devi scegliere combinazioni maggiori di 3, dovrai usare long o forse punto fisso int.