linjackson78 · October 11, 2016 04:14
diff --git a/combination.cpp b/combination.cpp
 #include <bitset>

 class Combination {
 public:
    
    // Throw exception when either m or n is invalid.
    // m should not be greater than 64, and n of course should be less than m.
    void init(int m, int n) {
        if (m > 64 || m < 0 || n > m || n <0) throw "Invalid m or n.";
        this->m = m;
        bits = (1ul << n) - 1;
        max = (1ul << m) - 1;
        hasNextCombination = true;
    }
    
    // Generate next combination.
    // Return false if there're no more combinations.
    // Result is store in argument "out".
    bool nextCombination(vector<int>& out) {
        out.clear();
        if (hasNextCombination) {
            bitset<64> bitset(bits);
            for (int i = 0; i < m; i ++) {
                if (bitset[i]) out.push_back(i);
            }
            hasNextCombination = next_combination(bits) && bits <= max;
            return true;
        } else {
            return false;
        }

    }

 private:
    int m;
    unsigned long bits;
    unsigned long max;
    bool hasNextCombination;
    
    // Credit to https://www.wikiwand.com/en/Combination
    bool next_combination(unsigned long& x) // assume x has form x'01^a10^b in binary
    {
        unsigned long u = x & -x; // extract rightmost bit 1; u =  0'00^a10^b
        unsigned long v = u + x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b
        if (v==0) // then overflow in v, or x==0
            return false; // signal that next k-combination cannot be represented
        x = v +(((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a+2}, and x ← x'100^b1^a
        return true; // successful completion
    }
 };

 // Usage:
 int main() {
    Combination combination;
    vector<int> data {1, 2, 3, 4};
    // Select combination of 3 element from data;
    combination.init(data.size(), 3);
    vector<int> result;
    while (combination.nextCombination(result)) {
        for (auto index : result) {
            cout << data[index] << " ";
        }
        cout << "\n";
    }
    // output:
    // 1 2 3
    // 1 2 4
    // 1 3 4
    // 2 3 4
 }
	#include <bitset>

	class Combination {
	public:

	// Throw exception when either m or n is invalid.
	// m should not be greater than 64, and n of course should be less than m.
	void init(int m, int n) {
	if (m > 64 \|\| m < 0 \|\| n > m \|\| n <0) throw "Invalid m or n.";
	this->m = m;
	bits = (1ul << n) - 1;
	max = (1ul << m) - 1;
	hasNextCombination = true;
	}

	// Generate next combination.
	// Return false if there're no more combinations.
	// Result is store in argument "out".
	bool nextCombination(vector<int>& out) {
	out.clear();
	if (hasNextCombination) {
	bitset<64> bitset(bits);
	for (int i = 0; i < m; i ++) {
	if (bitset[i]) out.push_back(i);
	}
	hasNextCombination = next_combination(bits) && bits <= max;
	return true;
	} else {
	return false;
	}

	}

	private:
	int m;
	unsigned long bits;
	unsigned long max;
	bool hasNextCombination;

	// Credit to https://www.wikiwand.com/en/Combination
	bool next_combination(unsigned long& x) // assume x has form x'01^a10^b in binary
	{
	unsigned long u = x & -x; // extract rightmost bit 1; u = 0'00^a10^b
	unsigned long v = u + x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b
	if (v==0) // then overflow in v, or x==0
	return false; // signal that next k-combination cannot be represented
	x = v +(((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a+2}, and x ← x'100^b1^a
	return true; // successful completion
	}
	};

	// Usage:
	int main() {
	Combination combination;
	vector<int> data {1, 2, 3, 4};
	// Select combination of 3 element from data;
	combination.init(data.size(), 3);
	vector<int> result;
	while (combination.nextCombination(result)) {
	for (auto index : result) {
	cout << data[index] << " ";
	}
	cout << "\n";
	}
	// output:
	// 1 2 3
	// 1 2 4
	// 1 3 4
	// 2 3 4
	}