1

私は反復的な解決策を知っています：

与えられたn要素のセット

を保存し、int v = 2^n これまでのすべてのバイナリ番号を生成しますv。

しかし、n> 32の場合はどうなるでしょうか？

すでに2^32のサブセットであることは知っていますが、それでも-32要素の制限を回避する方法は何ですか？

4

3 に答える 3

1

  1. 64アイテムの制限に満足している場合は、を使用できますlong。

  2. s/ sArrayListの配列/ 。次のような関数があります。intlongnext

    bool next(uint[] arr)
  for (int i = 0; i < arr.length; i++)
    if (arr[i] == 2^n-1) // 11111 -> 00000
      arr[i] = 0
    else
      arr[i]++
      return true
  return false // reached the end -> there is no next

  3. BitArray。おそらく、上記と比較してあまり効率的なオプションではありません。

    next最下位ビットを0から1に設定し、残りのすべてのビットを0に設定する関数を使用できます。例：

    10010 -> 10011
10011 -> 10100

注-サブセットが非常に多いという理由だけで、これにはおそらく永遠に時間がかかりますが、それは問題ではありません。

于 2013-02-09T12:55:10.047 に答える
0

この簡潔なHaskell実装のアナログを書くことができます：

powerSet = filterM (const [True, False])

filterMC＃に組み込みがないことを除いて。それは問題ありません、あなたはそれを自分で実装することができます。これが私の試みです：

public static IEnumerable<IEnumerable<T>> PowerSet<T>(IEnumerable<T> els)
{
    return FilterM(_ => new[] {true, false}, els);
}

public static IEnumerable<IEnumerable<T>> FilterM<T>(
    Func<T, IEnumerable<bool>> p,
    IEnumerable<T> els)
{
    var en = els.GetEnumerator();
    if (!en.MoveNext())
    {
        yield return Enumerable.Empty<T>();
        yield break;
    }

    T el = en.Current;
    IEnumerable<T> tail = els.Skip(1);
    foreach (var x in
        from flg in p(el)
        from ys in FilterM(p, tail)
        select flg ? new[] { el }.Concat(ys) : ys)
    {
        yield return x;
    }
}

そして、次のように使用できます。

foreach (IEnumerable<int> subset in PowerSet(new [] { 1, 2, 3, 4 }))
{
    Console.WriteLine("'{0}'", string.Join(",", subset));
}

ご覧のとおり、実装のどこでも明示的に使用されているintわけでも、明示的に使用されているわけでもないlongため、ここでの実際の制限は、現在のスタックサイズ制限で到達可能な最大再帰深度です。

UPD： Rosettaコードは非再帰的な実装を提供します：

public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(IEnumerable<T> input)
{
    var seed = new List<IEnumerable<T>>() { Enumerable.Empty<T>() }
        as IEnumerable<IEnumerable<T>>;

    return input.Aggregate(seed, (a, b) =>
        a.Concat(a.Select(x => x.Concat(new List<T> { b }))));
}
于 2013-02-09T13:31:43.373 に答える
0

次の方法でキャリービットを伝播することにより、@ biziclopアプローチを使用できます。長さKの32ビット「桁」のベクトルとして数値を格納します。したがって、2 ^（K * 32）サブセットとすべての増分を生成できます。操作は最大でO（K）操作を行います。私が考えることができるもう1つのことは、1つの配列にすべてのサブセットを生成する再帰的なバックトラックです。

于 2013-02-09T12:43:40.630 に答える