Permutazioni ma con alcuni numeri mantenuti in un ordine

Question

Ok, ho avuto una ricerca e ho cercato una soluzione C o python per questo problema. Preferirei python ... anche se è il mio linguaggio più debole (di 2 lingue molto deboli).

Un insieme di numeri, ad esempio 0 0 1 7 0 0 3 0 0 4

1. Trova tutte le permutazioni dell'insieme.
2. I numeri> 0 devono rimanere in quest'ordine (NON POSIZIONE!)
3. Deve esserci uno 0 tra i numeri, tuttavia uno 0 non è richiesto all'inizio e alla fine del set. Finché c'è ALMENO UNO 0 tra i numeri> 0.

Quindi in primo luogo, ho pensato di solo trovare tutte le possibili permutazioni e poi rimuovere la pula (controllando che se n> 0,! N + 1> 0) per ogni permutazione e quindi il primo numero> 0 == 1 , 2 ° #> 0 == 7 ecc. Ecc.

Mi sono poi fermato e ho pensato che fosse sciocco, diciamo che c'erano 12 numeri, che avrebbero dato 12! permutazioni. Questo nell'ordine di 500.000.000 di permutazioni di cui dovrei correre di nuovo per sbarazzarmi di pula.

Diciamo che ho avuto 40-50 serie di questi set di numeri da passare, questo è un bel colpo di tempo.

Esiste un modo più logico? Ho pensato di avere in qualche modo le permutazioni del python in qualche modo tenendo conto di quelle regole (se n> 0, n + 1 MUST == 0) e (n = primo numero, n2 = 2 ° ecc.)

Un esempio di un insieme ridotto sarebbe (non tutte le permutazioni, ma dà un'idea):

1,2,3,0,0,0,0,0

1. 1,0,2,0, 3,0,0,0
2. 0,1,0,2,0,3,0,0
3. 0,0,1,0,2,0,3,0
4. 0,0,1,0,0,2,0,3
5. 0,1,0,0,2,0,3,0

ecc ecc Quindi 1, 2,3 è in ordine ma gli "0" sono appena spostati?

Grazie!

Answer 1

In pratica si vuole ridurre il numero di combinazioni da calcolare raggruppando le cose in base ai loro invarianti. Dal momento che i numeri diversi da zero devono essere in un ordine fisso cominciamo con che:

1 2 3 

Dal momento che ci deve essere 0 di tra di loro aggiungerli in

1 0 2 0 3 

Ora che cosa si sono lasciati con è di tre 0 di per posizionare e hai bisogno di capire quante combinazioni danno sequenze distinte. Chiaramente da questo esempio le possibili posizioni che hai sono: prima del 1, tra il 1 e il 2, tra il 2 e il 3 e dopo il 3. Hai 4 posizioni in cui decidere come dividere i restanti tre 0. Questo è un combination problem with repetition, per cui la soluzione qui è (3 + 4 - 1) Choose 3 (che è 20).

Speriamo che il modo in cui ho affrontato questo problema di esempio sia sufficiente per generalizzare questo in sequenze arbitrarie, quindi lascerò che questo sia un esercizio per il lettore.

Answer 2

def find_permutations(l): 
    n = [e for e in l if e] # Strip zeros. 
    # Interspace non-zeros with zeros. 
    m = [j for i in n for j in (i,0)][:-1] 
    def fill(m): 
     if len(m) == len(l): 
      yield tuple(m) 
     else: 
      # Recursively fill with zeros. 
      for i in range(len(m)+1): 
       for o in fill(m[:i] + [0] + m[i:]): 
        yield tuple(o) 
    return sorted(set(fill(m))) 

Penso che questo dovrebbe coprirlo. Quindi, ad esempio (in python 3), potresti fare:

>>> [print(p) for p in find_permutations([1,2,3,0,0,0,0,0])] 
(0, 0, 0, 1, 0, 2, 0, 3) 
(0, 0, 1, 0, 0, 2, 0, 3) 
(0, 0, 1, 0, 2, 0, 0, 3) 
(0, 0, 1, 0, 2, 0, 3, 0) 
(0, 1, 0, 0, 0, 2, 0, 3) 
(0, 1, 0, 0, 2, 0, 0, 3) 
(0, 1, 0, 0, 2, 0, 3, 0) 
(0, 1, 0, 2, 0, 0, 0, 3) 
(0, 1, 0, 2, 0, 0, 3, 0) 
(0, 1, 0, 2, 0, 3, 0, 0) 
(1, 0, 0, 0, 0, 2, 0, 3) 
(1, 0, 0, 0, 2, 0, 0, 3) 
(1, 0, 0, 0, 2, 0, 3, 0) 
(1, 0, 0, 2, 0, 0, 0, 3) 
(1, 0, 0, 2, 0, 0, 3, 0) 
(1, 0, 0, 2, 0, 3, 0, 0) 
(1, 0, 2, 0, 0, 0, 0, 3) 
(1, 0, 2, 0, 0, 0, 3, 0) 
(1, 0, 2, 0, 0, 3, 0, 0) 
(1, 0, 2, 0, 3, 0, 0, 0) 

Era simile a quello che avevi in ​​mente?

Modifica: In pratica, ciò che la funzione chiamata fill fa è inserire uno zero tra ogni numero dell'elenco e recurse. Ogni volta che vengono registrati numeri sufficienti nella funzione fill (la lunghezza dell'elenco di numeri generati ricorsivamente equivale alla lunghezza dell'elenco di input originale) viene restituita una tupla di numeri.

L'unico motivo per la conversione in tuple al momento del reso è che il tipo deve essere lavabile da utilizzare in un set, come mostrato nell'ultima riga della funzione find_permutations. sorted è per gentilezza.