Decomposizione in più di divisori

Questo è effettivamente il partizionamento di un multiset di fattori primi.

Il semplice algoritmo per partizionare un intero è tramite una funzione ricorsiva che prende come parametri il valore che rimane alla partizione, la parte massima e gli accumulatori adatti. Per esempio. se la gestione della partizione finale viene eseguita con una funzione visit , quindi

_partitionInteger(int n, int maxPart, int[] accum)
    if (n == 0) visit(accum)
    else for (int m = 1; m <= maxPart; m++) _partitionInteger(n - m, m, accum :: m)

Questo è quindi avvolto per una bella presentazione come

partitionInteger(int n)
    _partitionInteger(n, n, [])

Esattamente lo stesso approccio funziona qui. La differenza è che invece di gestire interi si tratta di multiset. Invece di n == 0 vogliamo testare t == {} , e invece di iterare da 1 a maxPart abbiamo bisogno di scorrere i multiset in ordine lessicografico. Sarà più semplice rappresentarli in notazione di frequenza con un ordine di parti: per la tua applicazione, ciò significa che ciascun multiset è una sequenza ordinata di poteri primari. Se l'argomento n ha il suo primo valore diverso da zero alla posizione i , il multiset m su cui eseguiamo l'iterazione deve avere un valore diverso da zero alla posizione i : altrimenti non termineremo mai. (Questo è analogo all'avvio dell'iterazione su m = 1 anziché m = 0 ).

Quindi, per prendere l'esempio di 18 = 2^1 3^2 , le chiamate ricorsive sono:

_partition({2:1, 3:2}, {2:1, 3:2}, [])
    _partition({2:0, 3:2}, {2:1, 3:0}, [{2:1, 3:0}])
        _partition({2:0, 3:1}, {2:0, 3:1}, [{2:1, 3:0}, {2:0, 3:1}])
            _partition({2:0, 3:0}, {2:0, 3:1}, [{2:1, 3:0}, {2:0, 3:1}, {2:0, 3:1}])
                visit([{2:1, 3:0}, {2:0, 3:1}, {2:0, 3:1}])
        _partition({2:0, 3:0}, {2:0, 3:2}, [{2:1, 3:0}, {2:0, 3:2}])
            visit([{2:1, 3:0}, {2:0, 3:2}])
    _partition({2:0, 3:1}, {2:1, 3:1}, [{2:1, 3:1}])
        _partition({2:0, 3:0}, {2:0, 3:1}, [{2:1, 3:1}, {2:0, 3:1}])
            visit([{2:1, 3:1}, {2:0, 3:1}])
    _partition({2:0, 3:0}, {2:1, 3:2}, [{2:1, 3:2}])
        visit([{2:1, 3:2}])

In realtà scrivere i dettagli diventa un po 'più complicato, ma ad es. in Python otteniamo:

def partitionFactors(n):
    primes, powers, p = [], [], 2
    while p * p <= n:
        pow = 0
        while n % p == 0:
            n /= p
            pow += 1
        if pow > 0:
            primes.append(p)
            powers.append(pow)
        p += 1 + (p & 1)
    if n > 1:
        primes.append(n)
        powers.append(1)
    return partitionFactorsImpl(primes, powers, list(powers), [])

def partitionFactorsImpl(primes, powers, max, accum):
    curr, firstIdx = [0] * len(primes), 0
    while firstIdx < len(primes) and powers[firstIdx] == 0:
        firstIdx += 1

    if firstIdx == len(primes):
        yield list(accum)
        return

    curr[firstIdx] = 1
    while True:
        i, factor = firstIdx, 1
        while i < len(powers):
            factor *= int(primes[i] ** curr[i])
            powers[i] -= curr[i]
            i += 1

        accum.append(factor)
        for partition in partitionFactorsImpl(primes, powers, curr, accum):
            yield partition
        accum.pop()

        i = firstIdx
        while i < len(powers):
            powers[i] += curr[i];
            i += 1

        # Advance curr. This is effectively counting in a variable base to avoid exceeding the available powers.
        idx = len(powers) - 1
        while idx >= firstIdx:
            curr[idx] += 1
            if curr[idx] > powers[idx]:
                curr[idx] = 0
                idx -= 1
            else:
                break
        # There are two ways of running out of space
        # Note that the test 'curr > max' can probably be optimised
        if idx < firstIdx or curr > max:
            break

Output di esempio:

for x in partitionFactors(4 * 9 * 17):
    print (x)

dà

[2, 2, 3, 3, 17]
[2, 2, 51, 3]
[2, 2, 9, 17]
[2, 2, 153]
[34, 2, 3, 3]
[34, 2, 9]
[6, 2, 3, 17]
[6, 2, 51]
[6, 34, 3]
[6, 6, 17]
[102, 2, 3]
[102, 6]
[18, 2, 17]
[18, 34]
[306, 2]
[4, 3, 3, 17]
[4, 51, 3]
[4, 9, 17]
[4, 153]
[68, 3, 3]
[68, 9]
[12, 3, 17]
[12, 51]
[204, 3]
[36, 17]
[612]

(Si noti che il codice C # in una precedente revisione di questa risposta era buggato: l'errore è nel modo in cui max viene gestito).

In termini molto generali:

1. scrivi tutti i fattori primi del numero di interesse in un lungo array o elenco (cioè invece di [(2, 3) (5,2)], usa [2, 2, 2, 5, 5])
2. mappa una funzione su questa che restituisce tutte le possibili permutazioni di questa lista.
3. (per aumentare le prestazioni, filtrare i duplicati nell'elenco risultante di elenchi)
4. Mappa su ciascuno di questi elenchi permutati una funzione che restituisce tutti i diversi modi in cui l'elenco può essere diviso. (dopo il primo elem, il secondo, ... il n-1)
5. Per ogni divisione in ogni permutazione, prendi il prodotto di tutti i fattori nella divisione sinistra, prendi il prodotto di tutti i fattori nella divisione giusta.
6. Appiattisci l'elenco finale dell'elenco di coppie di numeri per finire con un elenco di coppie di numeri che insieme formeranno il numero richiesto.

Modifica: l'algoritmo sopra funziona se si desidera dividere con due numeri. Introducendo più split nel passaggio 4, puoi creare il resto dei risultati.

Ignorerò il fattore 1 perché potresti aggiungerlo tutte le volte che vuoi.

Per risolvere il problema è necessaria una procedura che produca l'elenco delle fatture di N con le aggiunte che richiedono che tutti i fattori siano inferiori o uguali a qualche M massimo.

Per produrre le fatture di N

• Crea l'elenco ordinato dei divisori.
• Ottieni il divisore più grande D.
• produce la lista di fatture di N con fattori < = D (vedi sotto)

Per produrre la fattorizzazione di N con fattori < = M:

• Per ogni divisore D se N con 1 < D < = M (usa la lista ordinata crea prima)
  • Se D = N, restituisci la fattorizzazione (D).
  • altro
    • Genera la fattorizzazione di N / D con fattori < = D (chiamata ricorsiva)
    • Aggiungi il fattore D alla fine di ciascuna fattorizzazione restituita
• raccoglie tutte le fatture dal loop in un unico elenco e restituiscile.

Potrebbe funzionare. Non l'ho ancora testato.