全ての組み合わせ in C# DouKaku?

2個以上のリストlist1, list2, list3...が与えられたときに、その複数個のリストの中の要素を一つずつとりだして組にする方法の全通りのリストを返すコードを書いてください。

Pythonで表現すると下のようになります。

>>> c = CrossProduct([1,2,3,4], "abc")
>>> list(c.all())
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'],
 [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'],
 [3, 'c'], [4, 'a'], [4, 'b'], [4, 'c']]

>>> c = CrossProduct([0, 1], "ab", ["Foo", "Bar"])
>>> list(c.all())
[[0, 'a', 'Foo'], [0, 'a', 'Bar'], [0, 'b', 'Foo'], [0, 'b', 'Bar']
 [1, 'a', 'Foo'], [1, 'a', 'Bar'], [1, 'b', 'Foo'], [1, 'b', 'Bar']]

順番はこの通りでなくても構いません。返すものはリストと書きましたが、なんらかの「一度に全部をメモリ上に作成しないリスト状のモノ」がある言語ではそちらを使う方がおすすめです。数値や文字列を一つのリストに混在させるのがやっかいな言語では整数のリストに限定しても構いません。

このお題はZIGOROuさんとのやりとりにヒントを得て作りました。 (しまった、先にブログで公開されてしまった→Yet Another Hackadelic - 直積の導出と考えうる全ての値を網羅したハッシュの生成)

追記：サンプル出力が間違っていたのでoceanさんの解答を使って出力し直しました。

using System;
using System.Collections;
using System.Collections.Generic;
class Program
{
  static void Main()
  {
    int[] ii = { 0, 1 };
    string[] ss = { "Foo", "Bar" };
    List<List<object>> lst = CrossProduct(ii, "ab".ToCharArray(), ss);
    foreach (List<object> l in lst)
    {
      foreach (object o in l) Console.Write(o + ", ");
      Console.WriteLine();
    }
  }
  static List<List<object>> CrossProduct(params IList[] lsts)
  {
    int[] pos = new int[lsts.Length];
    List<List<object>> lst = new List<List<object>>();
    int n1 = lsts.Length - 1;
    while (true)
    {
      List<object> l = new List<object>();
      for (int i = 0; i < lsts.Length; i++)l.Add(lsts[i][pos[i]]);
      lst.Add(l);
      int k = n1;
      while (k >= 0 && pos[k] == lsts[k].Count - 1) pos[k--] = 0;
      if (k < 0) break;
      ++pos[k];
    }
    return lst;
  }
}

もう１つおまけ

static List<List<object>> CrossProduct(params IList[] lsts)
{
  List<List<object>> lst = new List<List<object>>();
  lst.Add(new List<object>());
  foreach (IList il in lsts)
  {
    List<List<object>> l = new List<List<object>>();
    foreach (List<object> ls0 in lst)
    {
      foreach (object o in il)
      {
        List<object> ls = new List<object>(ls0);
        ls.Add(o);
        l.Add(ls);
      }
    }
    lst = l;
  }
  return lst;
}

イテレータその1

/// <summary>
/// 2つのIEnumerableを組合わせる
/// </summary>
public sealed class MulEnumerable<T, U> : IEnumerable<Pair<T, U>>
{
  private IEnumerable<T> ie1;
  private IEnumerable<U> ie2;
  /// <summary>コンストラクタ</summary>
  public MulEnumerable(IEnumerable<T> e1, IEnumerable<U> e2)
  {
    ie1 = e1;
    ie2 = e2;
  }
  /// <summary></summary>
  public IEnumerator<Pair<T, U>> GetEnumerator()
  {
    foreach (T t1 in ie1) foreach (U t2 in ie2)
        yield return new Pair<T, U>(t1, t2);
  }
  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  {
    return ((IEnumerable<Pair<T, U>>)this).GetEnumerator();
  }
}

イテレータその2

/// <summary>
/// 任意個のIEnumerableを組合わせる
/// </summary>
public sealed class MulEnumerable : IEnumerable<object[]>
{
  private System.Collections.IEnumerable[] ie;
  /// <summary>コンストラクタ</summary>
  public MulEnumerable(params System.Collections.IEnumerable[] e)
  {
    ie = e;
  }
  /// <summary></summary>
  public IEnumerator<object[]> GetEnumerator()
  {
    System.Collections.IEnumerator[] en = new System.Collections.IEnumerator[ie.Length];
    for (int i = 0; i < ie.Length; ++i)
      (en[i] = ie[i].GetEnumerator()).MoveNext();
    int n1 = ie.Length - 1;
    while (true)
    {
      object[] l = new object[ie.Length];
      for (int i = 0; i < ie.Length; ++i) l[i] = en[i].Current;
      yield return l;
      int k = n1;
      while (k >= 0 && !en[k].MoveNext())
      {
        en[k] = ie[k].GetEnumerator();
        en[k].MoveNext();
        --k;
      }
      if (k < 0) break;
    }
  }
  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  {
    return ((IEnumerable<object[]>)this).GetEnumerator();
  }
}

DouKaku?

全ての組み合わせ

Posted feedbacks - C#

Index

Feed

Other

Link

Pathtraq