Return to Question

EDIT: I have another way using bit operations, that is a bit less efficient I think, but maybe simpler... It uses a bitwise operation hack to check if the number of bits are equal to k elements (This can also be done less efficiently without the hack by converting the int to binary and then counting the 1's).

EDIT:

I have another way using bit operations, that is a bit less efficient I think, but maybe simpler... It uses a bitwise operation hack to check if the number of bits are equal to k elements (This can also be done less efficiently without the hack by converting the int to binary and then counting the 1's).

EDIT: I have another way using bit operations, that is a bit less efficient I think, but maybe simpler... It uses a bitwise operation hack to check if the number of bits are equal to k elements (This can also be done less efficiently without the hack by converting the int to binary and then counting the 1's).

    public List<int[]> GetAllCombinationsUsingBits(int[] array, int k)
    {
        var result = new List<int[]>();
        var len = array.Length;           
        var total = Math.Pow(2, len);

        for (int i = 1; i < total; i++)
        {
            // could also be checked by counting the ones in the binary, though this will require moving the binary up
            if (numberOfSetBits(i) == k) 
            {
                var element = new int[k];
                var binary = Convert.ToString(i, 2);
                var bLen = binary.Length;
                if ( bLen < len)
                    binary = PrependZero(binary, len - bLen);

                int counter = 0;
                for (int j = 0; j < len; j++)
                {
                    if (binary[j] == '1')
                    {
                        element[counter] = array[j];
                        counter++;
                    }
                }
                result.Add(element);
            }
        }

        return result;
    }

    private string PrependZero(string binary, int i)
    {            
        for (int j = 0; j < i; j++)
            binary = "0" + binary;

        return binary;
    }

    private int numberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

public class Combinations
{        
    private int[] _array; // holds the initial array; Assumed to contain different elements!!!
    private int _k; // the k elements needed to be chosen from that array
    private int[] _pushForward; // a kind of a counter to keep track how much we need to move forward each column
    private List<int[]> _results; // the results (all combinations); 
    private int[] _element; // the working element that is changed all the time

    public List<int[]> GetAllCombinations(int[] array, int k)
    {
        int len = array.Length;

        // basic sanity check
        if (len < k)
            throw new ArgumentException("Array length can't be less than number of selected elements");

        if (k < 1)
            throw new ArgumentException("Number of selected elements can't be less than 1");

        _array = array;
        _k = k;
        _results = new List<int[]>();
        _element = new int[k];
        _pushForward = new int[k]; // they are initialized to Zero already, no need to initialize again

        // the first element can move up to this position (in permutations); subsequent elements could move +1
        int maxStepsForward = len - _k + 1; 

        // entrance to recurssion method
        GetCombinations(0, maxStepsForward);

        return _results;
    }


    // col - the initial column handled in this recurse; can be between 0..k-1
    // maxSteps - correction for the max index; max index that this for loop can reach 
    private void GetCombinations(int col, int maxSteps)
    {
        for (int j = col + _pushForward[col]; j < maxSteps; j++)
        {
            // enter the corresponding column element
            _element[col] = _array[j]; 

            // if not in the last column enter recursion and move to next column
            if (col < _k - 1)
                GetCombinations(col + 1, maxSteps + 1);
            // else, just add the element
            else if (col == _k - 1)
            {
                // element is copied to new place in memory (shallow copy - works on ints) as working copy is constantly changed 
                int[] insert = new int[_k];
                _element.CopyTo(insert, 0);
                // new element is added to result list
                _results.Add(insert);
            }
        }
        // if we're out of the for loop, it means we finished a last-column cycle and need to push forward 
        // pushing forward is done for all elements in subsequent columns
        if (col > 0)
        {
            _pushForward[col - 1]++;
            for(int k = col; k < _pushForward.Length; k ++)
                _pushForward[k] = _pushForward[col - 1];
        }

    }
}

public class Combinations
{        
    private int[] _array; // holds the initial array; Assumed to contain different elements!!!
    private int _k; // the k elements needed to be chosen from that array
    private int[] _pushForward; // a kind of a counter to keep track how much we need to move forward each column
    private List<int[]> _results; // the results (all combinations); 
    private int[] _element; // the working element that is changed all the time

    public List<int[]> GetAllCombinations(int[] array, int k)
    {
        int len = array.Length;

        // basic sanity check
        if (len < k)
            throw new ArgumentException("Array length can't be less than number of selected elements");

        if (k < 1)
            throw new ArgumentException("Number of selected elements can't be less than 1");

        _array = array;
        _k = k;
        _results = new List<int[]>();
        _element = new int[k];
        _pushForward = new int[k]; // they are initialized to Zero already, no need to initialize again

        // the first element can move up to this position (in permutations); subsequent elements could move +1
        int maxStepsForward = len - _k + 1; 

        // entrance to recurssion method
        GetCombinations(0, maxStepsForward);

        return _results;
    }


    // col - the initial column handled in this recurse; can be between 0..k-1
    // maxSteps - correction for the max index; max index that this for loop can reach 
    private void GetCombinations(int col, int maxSteps)
    {
        for (int j = col + _pushForward[col]; j < maxSteps; j++)
        {
            // enter the corresponding column element
            _element[col] = _array[j]; 

            // if not in the last column enter recursion and move to next column
            if (col < _k - 1)
                GetCombinations(col + 1, maxSteps + 1);
            // else, just add the element
            else if (col == _k - 1)
            {
                // element is copied to new place in memory (shallow copy - works on ints) as working copy is constantly changed 
                int[] insert = new int[_k];
                _element.CopyTo(insert, 0);
                // new element is added to result list
                _results.Add(insert);
            }
        }
        // if we're out of the for loop, it means we finished a last-column cycle and need to push forward 
        // pushing forward is done for all elements in subsequent columns
        if (col > 0)
        {
            _pushForward[col - 1]++;
            for(int k = col; k < _k; k ++)
                _pushForward[k] = _pushForward[col - 1];
        }

    }
}