Pertanyaan Bagaimana Anda melakukan iterasi di atas sejumlah daftar sembarang, termasuk setiap permutasi?


Misalnya, jika saya memiliki dua daftar, saya akan:

foreach (Item item1 in lists[0])
  foreach (Item item2 in lists[1])
    // Do something with item1 and item2

Atau jika saya punya tiga, saya akan melakukannya

foreach (Item item1 in lists[0])
  foreach (Item item2 in lists[1])
    foreach (Item item3 in lists[2])
      // Do something with item1, item2, and item3

tetapi jika saya tidak tahu pada waktu kompilasi berapa banyak daftar di lists koleksi, bagaimana saya bisa dengan mudah mengulangi setiap permutasi?

Solusi C # sangat ideal, tetapi solusi dalam bahasa apa pun yang menunjukkan algoritma yang sesuai akan berguna.

Contoh 2 dimensi yang baik adalah daftar kolom dan daftar baris pada spreadsheet, di mana saya harus melakukan pemrosesan pada setiap sel. Ini masalah n-dimensi.


5
2017-10-10 16:30


asal


Jawaban:


Ada sebuah artikel yang bagus pada subjek oleh Eric Lippert.

saya sangat sarankan membaca artikel, karena menggambarkan proses yang Anda dapat tiba pada hasil, tetapi pada akhirnya kode yang dihasilkan pendek dan manis:

(Disalin kata demi kata dari tautan)

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this 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})); 
}

4
2017-10-10 16:50



    public static IEnumerable<T[]> IterateOverLists<T>(this IList<IEnumerable<T>> lists )
    {
        var array = new T[lists.Count];
        return IterateOverLists( lists, array, 0 );
    }
    private static IEnumerable<T[]> IterateOverLists<T>(this IList<IEnumerable<T>> lists, T[] array, int index)
    {
        foreach (var value in lists[index])
        {
            array[index] = value;
            if (index == lists.Count - 1)
            {
                // can make a copy of the array here too...
                yield return array;
            }
            else
            {
                foreach (var item in IterateOverLists(lists, array, index + 1))
                {
                    yield return item;
                }
            }
        }
    }

Jika salah satu daftar Anda kosong maka akan membunuh semuanya, tetapi Anda harus dapat mengatasi hal itu ...


1
2017-10-10 16:45



for (int i = 0; i < lists.Length; i++) {
    foreach (Item item in lists[i]) {
       ....
    }
}

0
2017-10-10 16:33