algoritmo per il calcolo delle permutazioni usando poca memoria?

-1

NON CHIEDI AL CODICE DI RISPONDERE A QUESTA SPECIFICA DOMANDA, CHIEDENDO COME APPROCCIO AL PROBLEMA IN GENERALE

c'è una domanda sui combattimenti di codice che richiede di trovare tutte le somme uniche di due matrici, una dimensione, l'altra quantità.

Sto usando un prodotto cartesiano per determinare tutte le possibili permutazioni. Questo sembra essere troppo sovraccarico. qualcuno ha commentato sul sito che qualcuno è stato in grado di farlo in ONE for loop.

Sto cercando una guida su come attaccare il problema da una CPU anziché dall'approccio alla memoria.

int possibleSums(int[] coins, int[] quantity) {
    var bitmaps = Enumerable.Range(1, Convert
                  .ToInt32(new string('1', coins.Length), 2))
        .Select(bm => Convert.ToString(bm, 2).PadLeft(coins.Length,'0'));

    var sums = coins
        .Select((c, i) => new {
            Index = i,
            Coin = c,
            Quantity = quantity[i]
        })
        .Select(cqi => new {
            cqi.Coin,
            cqi.Index,
            cqi.Quantity,
            CoinSums = Enumerable.Range(1, cqi.Quantity)
                                .Select(s => s * cqi.Coin)
        });
    var distinctSums = new HashSet<int>();
    foreach (var map in bitmaps)
    {
        var coinsUsed = new List<IEnumerable<int>>();
        for (var bitpos = 0; bitpos < map.Length; bitpos++)
        {
            if (map[bitpos] == '1')
            {
                coinsUsed.Add(sums.First(s => s.Index == bitpos).CoinSums);
            }
        }
        var coinSums =
            CartesianProduct(coinsUsed).Select(x => x.Sum());
        foreach (var sum in coinSums)
        {
            if (!distinctSums.Contains(sum))
                distinctSums.Add(sum);
        }
    }

    return distinctSums.Count();
}

IEnumerable<IEnumerable<T>> CartesianProduct<T>( IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>()};
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) => 
            from accseq in accumulator 
            from item in sequence 
            select accseq.Concat(new[] {item})                       
        );
 }
    
posta Chris 13.10.2017 - 00:15
fonte

2 risposte

2

Ci sono due approcci generali per risolvere questo problema nella memoria costante [1] :

[1]: tecnicamente O (n) memoria dove n è la lunghezza della permutazione, ma questo è molto meno di O (n · n!) che sarebbe richiesto per generare tutte le permutazioni in una sola volta.

  1. Definisci una mappatura biiettiva tra l'insieme delle permutazioni e i numeri naturali N = {1, 2, ..., n!} . Cioè dato un indice di permutazione i &in; N possiamo in qualche modo decodificarlo nella permutazione corrispondente. Quindi puoi semplicemente incrementare un contatore e ottenere la permutazione decodificata per generare tutte le permutazioni. Questo sembra possibile con un "sistema di numeri fattoriali": link

  2. Definisci un ordine totale su tutte le permutazioni, in modo da avere un concetto di permutazione "successiva". Iniziando con una prima permutazione conosciuta, puoi dare la permutazione successiva fino a quando non sei arrivato alla fine. Questo generalmente richiede che anche gli elementi permutati abbiano un ordine totale. Ad esempio, è possibile generare permutazioni in ordine lessicografico: link

Di questi approcci, generare permutazioni in ordine lessicografico è più semplice e più efficiente, ed è probabilmente l'approccio che useresti intuitivamente quando generi permutazioni a mano. Per esempio. quando permuti il set {a,b,c,d} dove a < b < c < d allora tutte le permutazioni in ordine lessicografico sono queste (leggi in termini di colonne):

abcd   bacd   cabd   dabc
abdc   badc   cadb   dacb
acbd   bcad   cbad   dbac
acdb   bcda   cbda   dbca
adbc   bdac   cdab   dcab
adcb   bdca   cdba   dcba
    
risposta data 13.10.2017 - 10:06
fonte
1

Possiamo utilizzare singoli bit raggruppati in numeri interi per calcolare permutazioni e combinazioni e per memorizzare lo stato intermedio richiesto per calcolare successivamente. Un intero incrementale può fare molto. Poiché le permutazioni e le combinazioni si espandono tanto rapidamente, un numero relativamente piccolo di bit può funzionare su uno spazio di ricerca abbastanza grande, generando molte combinazioni o permutazioni.

Tuttavia, se i tuoi bisogni superano le capacità degli interi (ad esempio 32 bit su alcuni processori o 64 bit su un altro), avrai bisogno di un altro approccio.

Il trucco, però - per usare una CPU più grezza e meno memoria - è usare bit in un tipo di dati intero nativo alla CPU, per mantenere lo stato intermedio e lasciare che la CPU lavori su gruppi di questi bit a dimensione intera una volta. Questo di solito significa fare cose in blocchi di 64 bit.

Quindi, dal punto di vista della CPU, sarebbe meglio usare due interi a 64 bit per 128 bit, se questo copre lo spazio di ricerca che stai cercando, piuttosto che andare a dati di dimensioni variabili (come in un tipo di stringa). L'utilizzo di dati di tipo stringa di dimensioni variabili significa praticamente allocazione della memoria e manipolazione del puntatore.

Dai un'occhiata a questa soluzione di combinazioni di qualche tempo fa, che in una classe contiene un intero / bit gestione basata sullo stato per combinazioni limitate a dimensioni inferiori a 65. Le permutazioni sono un superset di combinazioni; tuttavia, qualcosa di simile dovrebbe funzionare per loro.

    
risposta data 13.10.2017 - 05:40
fonte

Leggi altre domande sui tag