Come eseguire un'iterazione tra questi elementi

Question

Come eseguire un'iterazione tra questi elementi

#1 da (3 voti)
#2 da (2 voti)

2

Ho una serie di elementi:

int[] elem = new int[] {A, B, C};

Ho bisogno di calcolare la somma di TUTTE le combinazioni di quegli elementi, dove solo alcuni degli elementi possono essere selezionati facoltativamente. Userò la notazione:

{0,1} significa che l'elemento può essere selezionato o meno
{1} significa che l'elemento è sempre selezionato.

Pertanto, ho bisogno di calcolare il seguente valore, che potrebbe essere qualcosa del tipo:

result = {0,1}*A + {1}*B + {0,1}*C;

Ho provato ad usare nested per loops, in questo modo:

for (int i=0;i<2;i++)
    for (int j=1;j<2;j++) // notice I start at 1, not 0, because B is {1}
        for (int k=0;k<2;k++)
            Console.Write( i*A + j*B + k*C );

Ci sono due problemi con questo:

Questi loop nidificati sono piuttosto ingombranti
Il mio esempio ha solo tre elementi, ma la matrice potrebbe essere di qualsiasi dimensione. Ad esempio, se l'array avesse 10 elementi, avrei bisogno di avere 10 cicli annidati anziché tre. Non so cambiare il numero di cicli for in base alla dimensione dell'array.

Come eseguo l'iterazione per ottenere tutti i valori di somma per tutte le combinazioni in una matrice di dimensioni arbitrarie?

c# loops algorithms math

posta Juan Carlos Oropeza 20.05.2015 - 22:24

fonte

2 risposte

2

Questa è la mia risposta completa. Alla fine non ho capito la parte (i & mask >> j) quindi uso un IF. Per vedere se l'elem è parte della somma.

int[] elem = new int[] { 1, 2, 3, 4, 5 };
double maxElem = Math.Pow(2, elem.Length);

for (int first = 0; first < maxElem; first++)
{
    int mask = 1;
    int sum = 0;
    for (int run = 0; run < elem.Length; run++)
    {
        if ((first & mask) > 0)
        {
            sum += elem[run];                    
        }
        mask <<= 1;
    }
    Debug.Write(sum + " - ");
 }

Risultato

0 - 1 - 2 - 3 - 3 - 4 - 5 - 6 - 4 - 5 - 6 - 7 - 7 - 8 - 9 - 10 - 5 - 6 - 7 - 8 - 8 - 9 - 10 - 11 - 9 - 10 - 11 - 12 - 12 - 13 - 14 - 15

risposta data 21.05.2015 - 04:29

fonte

Leggi altre domande sui tag c# loops algorithms math

Come gestire un elenco aggregato dei campi di più oggetti? Quali usi ci sono oggi per scrivere manualmente Makefile? [chiuso]

score 3 · Accepted Answer

Stai calcolando la somma di tutte le combinazioni di un insieme di numeri.

Il numero di combinazioni che hai è 2 ⁿ, dove n è il numero di numeri. Ad esempio, se il tuo array avesse 5 elementi, sarebbe 2 ⁵ che è 32. Le combinazioni che andrà a scorrere sono le rappresentazioni binarie di 0..31.

00000
00001
00010
00011
...
11111

Questo ha il vincolo aggiuntivo che il valore deve essere .1... che può essere facilmente filtrato con una maschera di bit:

 for i = 0 .. 2**elem.size - 1
     next unless i & 0b01000

Dopo questo, cammini i bit e riassumi i valori:

    sum = 0
    mask = 0b00001  # written out, its just 1
    for j = 0 .. elem.size
        sum += elem[j] * ((i & mask) >> j)
        mask <<= 1
    print sum

Ammetto la possibilità che ci sia un fencepost o fuori da un errore, ma si tratta di loop abbastanza semplici che possono essere anche più semplici (o più difficili) a seconda del linguaggio di implementazione. Solo un po 'di matematica.

La parte fondamentale di questo è camminare sopra i bit di i . Iniziamo con un massimo con solo il bit più basso impostato ( 0b00001 che è anche solo un semplice vecchio 1 ). Quindi, per ciascun elemento dell'array, eseguire un bit per bit, della maschera e i . Se il bit è impostato, questa è una potenza di 2 (2 ⁰, 2 ¹, 2 ² ...) che abbiamo quindi per spostare indietro il numero di posizioni per renderlo 1 (se il bit è stato impostato) o 0 (se il bit non è stato impostato). Questo viene fatto con l'operatore >> . Questo potrebbe anche essere fatto dividendo per la potenza appropriata di 2.

Una volta ottenuto 1 o 0 dal bit matematico, moltiplicarlo per l'elemento nell'indice dell'array associato e quindi aggiungerlo alla somma.

Per passare alla posizione successiva, la maschera viene spostata a sinistra di un bit (in modo che 0b00001 diventi 0b00010 ), che può essere eseguita anche con *= 2 se non si desidera lavorare con i bit .