c# combination process time too slow and out of me

Question

I have n-elements of this kind

 public class Ricerca:IComparable
{
    public int id;

    public double Altezza;
    public double lunghezza;

    }

I need to calculate all the possible combination of this elements, my problem is that the method I am using is too slow when I have a lot of elements and sometimes I get the out of memory exception.

Any suggestions?

thanks for your help

this is how I calculate the combination I found this method in a c# forum I didn't do it

  public void allMyCombination(List<Ricerca>Elements,int i,ref List<List<Ricerca>> combinazioni)
    {

        Combinations<Ricerca> combinations = new Combinations<Ricerca>(Elements, i);


         foreach (Ricerca[] combination in combinations)
        {


            List<Ricerca> rsr = new List<Ricerca>() { };
            foreach (Ricerca rsh in combination)



            {

                rsr.Add(rsh);

            }

           // rsr.AddRange(combination);
            combinazioni.Add(rsr);


       }


    }

and these Are the classes used:

   class Combinations<T> : IEnumerable<T>
{
    #region Combinations Members
    private ElementSet<T> _Elements;
    private int _Choose;


    /// <param name="elements">the collection of elements</param>
    /// <param name="choose">the length of a combination</param>
    public Combinations(IEnumerable<T> elements, int choose)
        : this(new ElementSet<T>(elements, null), choose)
    {
    }


    /// <param name="elements">the collection of elements</param>
    /// <param name="choose">the length of a combination</param>
    /// <param name="comparer">the comparer used to order the elements</param>
    public Combinations(IEnumerable<T> elements, IComparer<T> comparer, int choose)
        : this(new ElementSet<T>(elements, comparer), choose)
    {
    }

    /// <param name="elements">the collection of elements</param>
    /// <param name="choose">the length of a combination</param>
    public Combinations(ElementSet<T> elements, int choose)
    {
        if (elements == null)
        {
            throw new ArgumentNullException("elements");
        }
        if (choose < 0 || choose > elements.Count)
        {
            throw new ArgumentOutOfRangeException("choose");
        }
        _Elements = elements;
        _Choose = choose;
    }
    #endregion

    #region IEnumerable<T[]> Members

    /// <seealso cref="IEnumerable{T}.GetEnumerator"/>
    public IEnumerator<T[]> GetEnumerator()
    {
        if (_Choose == 0)
        {
            return new ChooseZeroEnumerator();
        }
        else
        {
            return new Enumerator(this);
        }
    }
    #endregion

    #region IEnumerable Members
    IEnumerator IEnumerable.GetEnumerator()
    {
        return new Enumerator(this);
    }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        throw new NotImplementedException();
    }
    #endregion

    #region Enumerator Class
    private class Enumerator : IEnumerator<T[]>
    {
        #region Enumerator Members
        private Combinations<T> _Combinations;
        private int[] _Indices, _IndicesAt;
        private bool _PastEnd;

        internal Enumerator(Combinations<T> combinations)
        {
            _Combinations = combinations;
            _Indices = new int[_Combinations._Choose];
            _IndicesAt = new int[_Combinations._Elements.Elements.Count];
            Reset();
        }

        private void MoveFirst()
        {

            int currentIndex = 0;
            int usedCurrent = 0;
            for (int i = 0; i < _Indices.Length; i++)
            {
                Debug.Assert(currentIndex < _Combinations._Elements.Elements.Count);
                _Indices[i] = currentIndex;
                _IndicesAt[currentIndex]++;
                usedCurrent++;
                if (usedCurrent == _Combinations._Elements.Elements.Values[currentIndex])
                {

                    currentIndex++;
                    usedCurrent = 0;
                }
            }
        }

        private void MoveIndex(int index, int offset)
        {
            if (_Indices[index] >= 0 && _Indices[index] < _IndicesAt.Length)
            {
                _IndicesAt[_Indices[index]]--;
            }
            _Indices[index] += offset;
            if (_Indices[index] >= 0 && _Indices[index] < _IndicesAt.Length)
            {
                _IndicesAt[_Indices[index]]++;
            }
        }

        private bool IsFull(int position)
        {
            // True if (position) has as many indices as it can hold.
            return _IndicesAt[position] == _Combinations._Elements.Elements.Values[position];
        }

        private bool CanFitRemainingIndices(int index)
        {
            int space = _Combinations._Elements.ElementsAtOrAfter[_Indices[index]];
            return space >= _Indices.Length - index;
        }

        private bool AdvanceIndex(int index, int doNotReach)
        {
            // First move the index one position to the right.
            MoveIndex(index, 1);
            // If we've found an existing position with no other index, and there's room at-and-to-the-right-of us for all the indices greater than us, we're good.
            if (_Indices[index] < doNotReach)
            {
                if (_IndicesAt[_Indices[index]] == 1)
                {
                    if (CanFitRemainingIndices(index))
                    {
                        return true;
                    }
                }
            }
            // We've either fallen off the right hand edge, or hit a position with another index. If we're index 0, we're past the end of the enumeration. If not, we need to advance the next lower index, then push ourself left as far as possible until we hit another occupied position.
            if (index == 0)
            {
                _PastEnd = true;
                return false;
            }
            if (!AdvanceIndex(index - 1, _Indices[index]))
            {
                return false;
            }

            if (IsFull(_Indices[index] - 1))
            {
                _PastEnd = true;
                return false;
            }
            // Move left until the next leftmost element is full, or the current element has an index.
            do
            {
                MoveIndex(index, -1);
            } while (_IndicesAt[_Indices[index]] == 1 && !IsFull(_Indices[index] - 1));
            return true;
        }
        #endregion

        #region IEnumerator<T[]> Members
        public T[] Current
        {
            get
            {
                if (_Indices[0] == -1 || _PastEnd)
                {
                    // Before first or after last.
                    throw new InvalidOperationException();
                }
                else
                {
                    T[] current = new T[_Indices.Length];
                    for (int i = 0; i < _Indices.Length; i++)
                    {
                        current[i] = _Combinations._Elements.Elements.Keys[_Indices[i]];
                    }
                    return current;
                }
            }
        }
        #endregion

        #region IDisposable Members
        public void Dispose()
        {
            // Do nothing.
        }
        #endregion

        #region IEnumerator Members
        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }

        public bool MoveNext()
        {
            if (_PastEnd)
            {
                return false;
            }
            if (_Indices[0] == -1)
            {
                MoveFirst();
                return true;
            }
            else
            {
                bool ret = AdvanceIndex(_Indices.Length - 1, _IndicesAt.Length);
                return ret;
            }
        }

        public void Reset()
        {
            for (int i = 0; i < _Indices.Length; i++)
            {
                _Indices[i] = -1;
            }
            Array.Clear(_IndicesAt, 0, _IndicesAt.Length);
            _PastEnd = false;
        }
        #endregion
    }
    #endregion

    #region ChooseZeroEnumerator Class
    private class ChooseZeroEnumerator : IEnumerator<T[]>
    {
        #region ChooseZeroEnumerator Members
        private enum State
        {
            BeforeBeginning,
            OnElement,
            PastEnd,
        }

        private State _State;

        internal ChooseZeroEnumerator()
        {
            Reset();
        }
        #endregion

        #region IEnumerator<T[]> Members
        public T[] Current
        {
            get
            {
                if (_State == State.OnElement)
                {
                    return new T[0];
                }
                else
                {
                    throw new InvalidOperationException();
                }
            }
        }
        #endregion

        #region IDisposable Members
        public void Dispose()
        {
            // Do nothing.
        }
        #endregion

        #region IEnumerator Members
        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }

        public bool MoveNext()
        {
            switch (_State)
            {
                case State.BeforeBeginning:
                    _State = State.OnElement;
                    return true;

                case State.OnElement:
                case State.PastEnd:
                    _State = State.PastEnd;
                    return false;

                default:
                    throw new InvalidOperationException();
            }
        }

        public void Reset()
        {
            _State = State.BeforeBeginning;
        }
        #endregion
    }
    #endregion

}

  class ElementSet<T>
{
    private SortedList<T, int> _Elements;
    private int _Count;
    private int[] _ElementsAtOrAfter;

    /// <summary>
    /// Constructs a new <c>ElementSet</c> from a collection of elements, using the default comparer for the element type.
    /// </summary>
    /// <param name="elements">the elements</param>
    public ElementSet(IEnumerable<T> elements)
        : this(elements, null)
    {
    }

    /// <summary>
    /// Constructs a new <c>ElementSet</c> from a collection of an elements, using a custom comparer.
    /// </summary>
    /// <param name="elements">the elements</param>
    /// <param name="comparer">the comparer</param>
    public ElementSet(IEnumerable<T> elements, IComparer<T> comparer)
    {
        if (elements == null)
        {
            throw new ArgumentNullException("elements");
        }

        SortedDictionary<T, int> sorted = new SortedDictionary<T, int>(comparer);
        foreach (T element in elements)
        {
            int count;
            if (sorted.TryGetValue(element, out count))
            {
                sorted[element] = count + 1;
            }
            else
            {
                sorted[element] = 1;
            }
            _Count++;
        }
        _Elements = new SortedList<T, int>(sorted, comparer);
        _Elements.Capacity = _Elements.Count;
        // Produce the Number of Elements At or After array.
        // This is a cumulative sum of the reverse of the values array.
        if (_Elements.Count > 0)
        {
            _ElementsAtOrAfter = new int[_Elements.Count];
            _ElementsAtOrAfter[_Elements.Count - 1] = _Elements.Values[_Elements.Count - 1];
            for (int i = _Elements.Count - 2; i >= 0; i--)
            {
                _ElementsAtOrAfter[i] = _ElementsAtOrAfter[i + 1] + _Elements.Values[i];
            }
        }
    }

    internal SortedList<T, int> Elements
    {
        get
        {
            return _Elements;
        }
    }

    internal int Count
    {
        get
        {
            return _Count;
        }
    }

    internal int[] ElementsAtOrAfter
    {
        get
        {
            return _ElementsAtOrAfter;
        }
    }

}

Answer 1

Nice class you found ! Did some testing with it. I added a comparer to your element class. Don't know what your comparer looks like.. but maybe speed can be improved by optimizing it. For my tests, I kept it minimal. See code below.

public class Ricerca : IComparable
{
    public double altezza;
    public double lunghezza;

    // added some index to sort by
    public int i = 0;
    public Ricerca(int ci) { altezza = 53; lunghezza = -4.5;  i = ci; }

    // comparator to sort with
    public int CompareTo(object e)
    { return (((Ricerca)e).i > i) ? 1 : (((Ricerca)e).i == i) ? 0 : -1; }
}

Two observations,

1. above remarks about zillions of permutations only count when all elements are different. When there are many equal values in the list, the result count is much smaller and operation is much faster. So if this generic class is usable for you, depends not only on list counts, also on the data you are analysing..

2. this is managed code, so memory usage depends on GC. When all indexes are unique, I get 10015005 sets for (29 9), 24 sec runtime and about 900MB consumption. When every second index is equal, I get 0.7 sec runtime and 48MB consumption. You can eliminate this load, when you don't translate the Combinations list to another list, but use the foreach() on combinations itself. My test shows constant memory use, because I dont store the list, I get constant memory consumption of about 18MB with below loop irrespective of parameters. for Elements.Count=29, set size 9 it needs 12 sec.

   private void doSomething(List<Ricerca> AChosen)
   {
       // perform some task on chosen set
   }
   
   void Test(List<Ricerca> Elements, int rSetSize)
   {
    Combinations<Ricerca> combinations = new Combinations<Ricerca>(Elements, rSetSize);
    int nReported = 0;
    foreach (Ricerca[] combination in combinations)
    {
       List<Ricerca> chosenPlaces = new List<Ricerca>();
       for (int j = 0; j < combination.Length; j++)
           chosenPlaces.Add(combination[j]);
       doSomething(chosenPlaces); // instance, save only when needed
       nReported++;
    }
   

   }