Combinatoria con caratteri ripetuti sul gruppo iniziale

Question

Lo so se ho il seguente gruppo di numeri

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Posso avere 5040 numeri diversi a 4 cifre, usando 10!/ (10 - 4)!

Ma se ripeto un numero del gruppo iniziale, tipo

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Quanti numeri diversi di 4 cifre possiamo costruire?So che la risposta è 3360, ma non so come implementarla.

Importante:In questo caso, numeri come "1123" o "1213" dovrebbero essere combinazioni valide, ma non "1113", poiché ce ne sono solo due nel gruppo iniziale.

Anche per il gruppo

{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }

Dovrebbero esserci 2190 numeri a 4 cifre.Qualche idea su come calcolare queste risposte?

Questo non è un compito a casa, otterrò questi numeri da un hardware specifico e, a seconda del numero di combinazioni, restituirò alcuni dati.

Answer 1

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Qui si sceglie quattro numeri da dieci e possono essere qualsiasi ordine. Quindi la soluzione è

(10 choose 4) * 4! = 5040.

Ora consideriamo il caso di

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Ci sono alcune combinazioni qui. Siamo in grado di avere zero 1s, uno o due 1 1s. Nel primo caso ci sono

(8 choose 4) * 4!

combinazioni possibili. Nel secondo caso ci sono

(8 choose 3) * 4!

combinazioni possibili. Nel terzo caso ci sono

(8 choose 2) * 4! / 2!

combinazioni possibili. Quest'ultimo richiede una spiegazione. Ci sono otto possibili non 1 cifra tra cui scegliere e ci stanno scegliendo due. Le due cifre rimanenti sono 1s (per ipotesi che siamo nel caso in cui sono i nostri 4 corde contiene due 1s). Siamo in grado di mettere queste quattro cifre in qualsiasi ordine ma le 1s sono intercambiabili così dividiamo per il numero di possibili ordinamenti dei 1s (2!).

Quindi la risposta è

(8 choose 4) * 4! + (8 choose 3) * 4! + (8 choose 2) * 4! / 2! = 3360.

Per il caso di

{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }

ci sono ancora un paio di combinazioni. Possiamo avere zero 1s e zero 2s, uno 1 e zero 2s, due 1s e zero 2s, due 1s e una 2, due 1s e due 2s, zero 1s e una 2, zero 1s e due 2s, una 1 e due 2s , e un 1 ed una 2. Questi può essere lavorato come sopra e la risposta finale è

(6 choose 4) * 4!
    + 2 * (6 choose 3) * 4!
    + 2 * (6 choose 2) * 4! / 2!
    + (6 choose 2) * 4!
    + 2 * (6 choose 1) * 4! / 2!
    + (6 choose 0) * 4! / (2! * 2!)
= 2190.

Questo è un approccio abbastanza semplicistico ai problemi di questo tipo. Ci sono altri (ad esempio, inclusione / esclusione ) che sono più sofisticati, ma la corrente approccio è il più facile da capire se stai vedendo problemi di questo tipo per la prima volta.

Answer 2

Si potrebbe desiderare di fare riferimento a questo straordinario Combinatorics implementazione.

Answer 3

Sarebbe abbastanza semplice senza duplicazioni...per

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Dato che hai solo 9 scelte distinte (invece delle 10 del problema originale), la risposta dovrebbe essere 9!/ (9 - 4)!

(A proposito, puoi effettivamente avere più numeri diversi a 4 cifre se consenti la ripetizione, ad es.4456.Allora la risposta sarebbe semplicemente 9^4 numeri di 4 cifre.)

Allo stesso modo, {1, 1, 2, 2, 3, 4, 5, 6, 7, 8 } ha 8 scelte distinte, quindi la risposta dovrebbe essere 8!/ (8 - 4)!secondo i tuoi calcoli originali.

Modifica e risposta effettiva:Forse volevi dire che se l'1 è duplicato nel tuo set, puoi usare due 1 nella risposta?

Modifica 2:Modulo Python funzionante e testato fornito

In tal caso, potresti provare a calcolare il numero distinto di possibilità e quindi ad aggiungere i risultati con i duplicati, come suggerisce il seguente codice Python):

import math

def set_exclude(a, b):
    result = []
    for i in a:
        if not i in b:
            result.append(i)
    return result

def cnt_unique(aset, choices_picked, count_left, count_total):
    # Sanity check
    if count_left < 0:
        return 0
    if count_left == 0:
        return math.factorial(count_total)
    # Do non-duplicate combinations first
    # Set unprocessed = (set without any elements in choices_picked)
    unprocessed = set_exclude(aset, choices_picked)
    temp = len(set(unprocessed))

    # If we have no more valid items to choose from, this is impossible
    if temp >= count_left:
        result = math.factorial(temp) / math.factorial(temp - count_left) / \
                 math.factorial(count_left) * math.factorial(count_total)
    else:
        result = 0

    # Now find duplicate-involving combinations
    for member in set(unprocessed):
        valid = True
        for contest in choices_picked:
            if contest >= member:
                valid = False
                break

        if valid:
            count = unprocessed.count(member)
            new_choices = choices_picked + [ member ]
            for i in range(2, count+1):
                result_temp = cnt_unique(aset, new_choices, \
                  count_left - i, count_total)
                if result_temp != 0:
                    result_temp //= math.factorial(i)
                    result += result_temp
    return result

aset = [ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
result_size = 4
combinations = cnt_unique(aset, [], result_size, result_size)

OK, ho verificato manualmente che l'algoritmo funziona per tutti i casi presentati sopra.Sono abbastanza fiducioso che funzioni in casi più generali, ma al momento non ho tempo per eseguire ulteriori casi di test (ad esempio, se ci fossero 3 1 o 3 gruppi di duplicati).Nota che esploderebbe anche se nel set non ci fossero numeri che non fossero in scelte_picked (cioè hai un numero univoco duplicato 10 volte).

Modifica 3:Per quanto riguarda quante chiamate di funzione vengono effettuate con questo algoritmo per insiemi di grandi dimensioni, ho testato con la seguente chiamata di funzione, incrementando una variabile una volta per ogni chiamata non banale (count_left >= 0) a cnt_unique:

>>> def test():
        b = [0]
        c = time.time()
        result = cnt_unique(range(1,51) + range(1,51), [], 4, 4, b)
        c = time.time() - c
        print("Result: " + str(result))
        print("Time: " + str(c))
        print("Calls: " + str(b[0]))

>>> test()
Result: 6240150
Time: 0.0150001049042
Calls: 1276

Pertanto, per un set di 100 elementi con 2 voci per ciascun numero da 1 a 50, sono state effettuate 1276 chiamate.Ed esegue abbastanza velocemente;un tick con time.time() è 15 ms, quindi viene eseguito in genere in meno di 15 ms.

Answer 4

Se avete bisogno di fare questo su qualsiasi set più grande del vostro esempio, guardare fuori per overflow nei calcoli intermedi. 13! è già abbastanza grande da traboccare a 32 bit UINT. Solo pochi più grande di quello traboccherà 64 bit. Utilizzando float / double non è niente di meglio da quando si otterrà una risposta sbagliata senza la piena precisione.

Si avrebbe bisogno di utilizzare una classe di precisione intero arbitrario o qualche classe numerico personalizzato che trasporta l'elenco completo dei fattori nel calcolo del fattoriale o qualsiasi moltiplica, poi facendo eliminazione fattore per semplificare la divisione.

Answer 5

È necessario rompere il problema in 2 casi:

Caso 1: zero o uno "1" nel vostro numero a 4 cifre Numero di permutazione è 9! / (9-4)! = 3024

Caso 2: due "1" s nel numero di 4 cifre Sai due delle cifre deve essere 1, quindi non ci sono 8 * 7 modi per selezionare i restanti due cifre. E ci sono (4! / 2!) Modi per organizzare le due "1" s ed altre due cifre. Quindi, il numero di permutazione è 8 * 7 * (4! / 2!) = 672

Sembra che la risposta è 3024 + 672 = 3696