source: branches/HeuristicLab.VariableInteractionNetworks/HeuristicLab.VariableInteractionNetworks/3.3/TinySet.cs @ 13788

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace HeuristicLab.VariableInteractionNetworks {
  internal static class Util {
    public static IEnumerable<IEnumerable<T>> Combinations<T>(IList<T> items, int k) {
      if (k < 0)
        throw new InvalidOperationException();
      if (items == null)
        throw new ArgumentNullException("items");
      int n = items.Count;
      if (n > TinySet.Maximum)
        throw new InvalidOperationException();
      return
        from combination in Combinations(n, k)
        select (from index in combination select items[index]);
    }

    // Takes integers n and k, both non-negative.
    // Produces all sets of exactly k elements consisting only of 
    // integers from 0 through n - 1.
    private static IEnumerable<TinySet> Combinations(int n, int k) {
      // Base case: if k is zero then there can be only one set
      // regardless of the value of n: the empty set is the only set
      // with zero elements.
      if (k == 0) {
        yield return TinySet.Empty;
        yield break;
      }

      // Base case: if n < k then there can be no set of exactly
      // k elements containing values from 0 to n - 1, because sets
      // do not contain repeated elements.

      if (n < k)
        yield break;

      // A set containing k elements where each is an integer from
      // 0 to n - 2 is also a set of k elements where each is an
      // integer from 0 to n - 1, so yield all of those.

      foreach (var r in Combinations(n - 1, k))
        yield return r;

      // If we add n - 1 to all the sets of k - 1 elements where each
      // is an integer from 0 to n - 2, then we get a set of k elements
      // where each is an integer from 0 to n - 1.

      foreach (var r in Combinations(n - 1, k - 1))
        yield return r.Add(n - 1);
    }
  }

  internal struct TinySet : IEnumerable<int> {
    public static readonly TinySet Empty = new TinySet(0);
    public const int Minimum = 0;
    public const int Maximum = 31;
    private readonly int bits;
    private TinySet(int bits) { this.bits = bits; }
    public bool Contains(int item) {
      if (item < Minimum || item > Maximum)
        return false;
      return (bits & (1 << item)) != 0;
    }
    public TinySet Add(int item) {
      if (item < Minimum || item > Maximum)
        throw new InvalidOperationException();
      return new TinySet(bits | (1 << item));
    }
    public TinySet Remove(int item) {
      if (item < Minimum || item > Maximum)
        return this;
      return new TinySet(bits & ~(1 << item));
    }
    IEnumerator IEnumerable.GetEnumerator() {
      return this.GetEnumerator();
    }
    public IEnumerator<int> GetEnumerator() {
      for (int item = Minimum; item <= Maximum; ++item)
        if (Contains(item))
          yield return item;
    }
  }
}