efficiente calcolare prossima permutazione di lunghezza k da scelte n

Question

ho bisogno di efficiente calcolare la prossima permutazione di lunghezza k da n scelte. Liste di Wikipedia a great algorithm per il calcolo della prossima permutazione di lunghezza n da n scelte.

La cosa migliore che posso venire con sta usando tale algoritmo (o the Steinhaus–Johnson–Trotter algorithm), e poi basta considerare solo i primi k elementi della lista, e l'iterazione di nuovo ogni volta che i cambiamenti sono tutti sopra quella posizione.

Vincoli:

• L'algoritmo deve calcolare il prossimo permutazione dato niente di più che la permutazione corrente. Se è necessario generare un elenco di tutte le permutazioni, occuperà troppa memoria.
• Deve essere in grado di calcolare una permutazione di lunghezza solo k di n (questo è dove l'altro algoritmo fallisce

Non vincoli:

• Non importa se si tratta di in- o che non
• non mi importa se è in ordine lexographical, o qualsiasi ordine per quella materia
• non mi interessa troppo quanto efficientemente calcola la prossima permutazione, entro ragione, naturalmente, non può darmi la prossima permutazione creando una lista di tutti i possibili ogni possibile.

Answer 1

È possibile rompere questo problema in due parti:

1) Trova tutti i sottoinsiemi di dimensioni k da un insieme di dimensioni n.

2) Per ogni sottogruppo di questo tipo, trovare tutte le permutazioni di un sottogruppo di dimensioni k.

L'articolo di riferimento di Wikipedia fornisce un algoritmo per la parte 2, quindi non lo ripeterò qui. L'algoritmo per la parte 1 è piuttosto simile. . Per semplicità, io descrivo per "trovare tutti i sottoinsiemi di dimensioni k degli interi [0...n-1]

1) Inizia con il sottoinsieme [0...k-1]

2) Per ottenere il prossimo sottoinsieme, dato un sottoinsieme S:

2a) Trovare il più piccolo j tale che j ∈ S ∧ j+1 ∉ S Se j == n-1, non v'è alcun sottoinsieme successivo,.. abbiamo finito

2b) Gli elementi meno di j forma una sequenza i...j-1 (poiché se uno di questi valori mancava, j non sarebbe minimo). Se i non è 0, sostituire questi elementi con i-i...j-i-1. Sostituire l'elemento j con l'elemento j+1.