# The Array power set is stolen from http://snippets.dzone.com/posts/show/3524
class Array
  # Returns the "power set" for this Array. This means that an array with all
  # subsets of the array's elements will be returned.
  def power_set
    # the power set line is stolen from http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/
    inject([[]]){|c,y|r=[];c.each{|i|r<<i;r<<i+[y]};r}
  end
end

class Hash
  def power_set
    # Returns the "power set" for this Hash. This means that a array with hashes of all
    # subsets of the hash's (key => value) pairs will be returned.
    # Example:
    # >> {:feedback_type=>"", :language_code=>"", :comment=>""}.power_set
    #
    # [{}, {:comment=>""}, {:language_code=>""}, {:language_code=>"", :comment=>""}, {:feedback_type=>""}, {:feedback_type=>"", :comment=>""}, {:feedback_type=>"", :language_code=>""}, {:feedback_type=>"", :language_code=>"", :comment=>""}]
    
    hash_to_array = self.to_a
    array_power_set = hash_to_array.power_set
    hash_power_set = array_power_set.collect { |pairs| pairs.inject({}) { |hash,pair| hash[pair[0]] = pair[1]; hash } }
    hash_power_set
  end
end

#include <stdio.h>

/* Prints out a combination like {1, 2} */
void printc(int comb[], int k) {
	printf("{");
	int i;
	for (i = 0; i < k; ++i)
		printf("%d, ", comb[i] + 1);
	printf("\b\b}\n");
}

/*
	next_comb(int comb[], int k, int n)
		Generates the next combination of n elements as k after comb

	comb => the previous combination ( use (0, 1, 2, ..., k) for first)
	k => the size of the subsets to generate
	n => the size of the original set

	Returns: 1 if a valid combination was found
		0, otherwise
*/
int next_comb(int comb[], int k, int n) {
	int i = k - 1;
	++comb[i];
	while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
		--i;
		++comb[i];
	}

	if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
		return 0; /* No more combinations can be generated */

	/* comb now looks like (..., x, n, n, n, ..., n).
	Turn it into (..., x, x + 1, x + 2, ...) */
	for (i = i + 1; i < k; ++i)
		comb[i] = comb[i - 1] + 1;

	return 1;
}

int main(int argc, char *argv[]) {
	int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */
	int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
	int comb[16]; /* comb[i] is the index of the i-th element in the
			combination */

	/* Setup comb for the initial combination */
	int i;
	for (i = 0; i < k; ++i)
		comb[i] = i;

	/* Print the first combination */
	printc(comb, k);

	/* Generate and print all the other combinations */
	while (next_comb(comb, k, n))
		printc(comb, k);

	return 0;
}