How can I iterate throught every possible combinat

问题:

How can I loop through all combinations of n playing cards in a standard deck of 52 cards?

回答1:

You need all combinations of n items from a set of N items (in your case, N == 52, but I'll keep the answer generic).

Each combination can be represented as an array of item indexes, size_t item[n], such that:

• 0 <= item[i] < N
• item[i] < item[i+1], so that each combination is a unique subset.

Start with item[i] = i. Then to iterate to the next combination:

• If the final index can be incremented (i.e. item[n-1] < N-1), then do that.
• Otherwise, work backwards until you find an index that can be incremented, and still leave room for all the following indexes (i.e. item[n-i] < N-i). Increment that, then reset all the following indexes to the smallest possible values.
• If you can't find any index that you can increment (i.e. item[0] == N-n), then you're done.

In code, it might look something vaguely like this (untested):

void first_combination(size_t item[], size_t n)
{
    for (size_t i = 0; i < n; ++i) {
        item[i] = i;
    }
}

bool next_combination(size_t item[], size_t n, size_t N)
{
    for (size_t i = 1; i <= n; ++i) {
        if (item[n-i] < N-i) {
            ++item[n-i];
            for (size_t j = n-i+1; j < n; ++j) {
                item[j] = item[j-1] + 1;
            }
            return true;
        }
    }
    return false;
}

It might be nice to make it more generic, and to look more like std::next_permutation, but that's the general idea.

回答2:

This combinations iterator class is derived from the previous answers posted here.

I did some benchmarks and it is a least 3x faster than any next_combination() function you would have used before.

I wrote the code in MetaTrader mql4 to do testing of triangular arbitrage trading in forex. I think you can port it easily to Java or C++.

class CombinationsIterator
{
private:
	int input_array[];
	int index_array[];
	int m_indices;      // K
	int m_elements;     // N

public:
	CombinationsIterator(int &src_data[], int k)
	{
		m_indices = k;
		m_elements = ArraySize(src_data);
		ArrayCopy(input_array, src_data);
		ArrayResize(index_array, m_indices);

		// create initial combination (0..k-1)
		for (int i = 0; i < m_indices; i++)
		{
			index_array[i] = i;
		}
	}

	// https://stackoverflow.com/questions/5076695
	// bool next_combination(int &item[], int k, int N)
	bool advance()
	{
		int N = m_elements;
		for (int i = m_indices - 1; i >= 0; --i)
		{
			if (index_array[i] < --N)
			{
				++index_array[i];
				for (int j = i + 1; j < m_indices; ++j)
				{
					index_array[j] = index_array[j - 1] + 1;
				}
				return true;
			}
		}
		return false;
	}

	void get(int &items[])
	{
		// fill items[] from input array
		for (int i = 0; i < m_indices; i++)
		{
			items[i] = input_array[index_array[i]];
		}
	}
};

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above class

#define N 5
#define K 3

void OnStart()
{
	int x[N] = {1, 2, 3, 4, 5};

	CombinationsIterator comboIt(x, K);

	int items[K];

	do
	{
		comboIt.get(items);

		printf("%s", ArrayToString(items));

	} while (comboIt.advance());

}

Output:

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

回答3:

I see this problem is essentially the same as the power set problem. Please see Problems with writing powerset code to get an elegant solution.

回答4:

#include <iostream>
#include <vector>
using namespace std;

class CombinationsIndexArray {
    vector<int> index_array;
    int last_index;
    public:
    CombinationsIndexArray(int number_of_things_to_choose_from, int number_of_things_to_choose_in_one_combination) {
        last_index = number_of_things_to_choose_from - 1;
        for (int i = 0; i < number_of_things_to_choose_in_one_combination; i++) {
            index_array.push_back(i);
        }
    }
    int operator[](int i) {
        return index_array[i];
    }
    int size() {
        return index_array.size();
    }
    bool advance() {

        int i = index_array.size() - 1;
        if (index_array[i] < last_index) {
            index_array[i]++;
            return true;
        } else {
            while (i > 0 && index_array[i-1] == index_array[i]-1) {
                i--;
            }
            if (i == 0) {
                return false;
            } else {
                index_array[i-1]++;
                while (i < index_array.size()) {
                    index_array[i] = index_array[i-1]+1;
                    i++;
                }
                return true;
            }
        }
    }
};

int main() {

    vector<int> a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    a.push_back(5);
    int k = 3;
    CombinationsIndexArray combos(a.size(), k);
    do  {
        for (int i = 0; i < combos.size(); i++) {
            cout << a[combos[i]] << " ";
        }
        cout << "\n";
    } while (combos.advance());

    return 0;
}

Output:

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5