N choose k python list

I'm attempting to generate all n choose k combinations of a list (not checking for uniqueness) recursively by following the strategy of either include or not include an element for each recursive call. I can definitely print out the combinations but I for the life of me cannot figure out how to return the correct list in Python. Here are some attempts below:

class getCombinationsClass:

    def __init__(self,array,k):

        #initialize empty array
        self.new_array = []
        for i in xrange(k):
            self.new_array.append(0)

        self.final = []

        self.combinationUtil(array,0,self.new_array,0,k)

    def combinationUtil(self,array,array_index,current_combo, current_combo_index,k):

        if current_combo_index == k:
            self.final.append(current_combo)
            return

        if array_index >= len(array):
            return

        current_combo[current_combo_index] = array[array_index]

        #if current item included
        self.combinationUtil(array,array_index+1,current_combo,current_combo_index+1,k)

        #if current item not included
        self.combinationUtil(array,array_index+1,current_combo,current_combo_index,k)

In the above example I tried to append the result to an external list which didn't seem to work. I also tried implementing this by recursively constructing a list which is finally returned:

def getCombinations(array,k):

    #initialize empty array
    new_array = []
    for i in xrange(k):
        new_array.append(0)

    return getCombinationsUtil(array,0,new_array,0,k)

def getCombinationsUtil(array,array_index,current_combo, current_combo_index,k):

    if current_combo_index == k:
        return [current_combo]

    if array_index >= len(array):
        return []

    current_combo[current_combo_index] = array[array_index]

    #if current item included & not included
    return getCombinationsUtil(array,array_index+1,current_combo,current_combo_index+1,k) + getCombinationsUtil(array,array_index+1,current_combo,current_combo_index,k)

When I tested this out for the list [1,2,3] and k = 2, for both implementations, I kept getting back the result [[3,3],[3,3],[3,3]]. However, if I actually print out the 'current_combo' variable within the inner (current_combo_index == k) if statement, the correct combinations print out. What gives? I am misunderstanding something to do with variable scope or Python lists?

Suppose that I have a 1-D list called myList. Here's an example:

myList = {"A", "B", "C", "D"};

I want to write (or find built-in) a function called getConfigurations that will return all possible "n choose k" lists. Before I explain what I mean by an "n choose k" list, let me just write down the result I would like to obtain from getConfigurations for the list myList given above:

getConfigurations[myList]

{

  (* configurations when ONE element is chosen: k=1 *)
 {{"A"}, {"B"}, {"C"}, {"D"}}, 

  (* configurations when TWO elements are chosen: k=2 *)
 {{"A", "B"}, {"A", "C"}, {"A", "D"}, {"B", "C"}, {"B", "D"}, {"C", "D"}},

  (* configurations when THREE elements are chosen: k=3 *)
 {{"A", "B", "C"}, {"A", "B", "D"}, {"A", "C", "D"}, {"B", "C", "D"}},

  (* configurations when FOUR elements are chosen: k=4 *)
 {{"A", "B", "C", "D"}} 

 }

I am not sure what (if anything) this is called in combinatorics, but it reminds me of the binomial coefficient:

$${n \choose k} = \frac{n!}{k! (n-k)!}$$

which I remember being called the "n choose k" binomial coefficient.

In the example myList given above, $n = 4$ because Length[myList] is 4. For each value of k ($k = 1, 2, 3, 4$), I want to generate all possible configurations. In my case, order does not matter, so for example, {"B", "A"} is indistinguishable from {"A", "B"}.

I think that the formula for $n \choose k$ gives the number of configurations. It turns out that

$${4 \choose 1} = 4$$ $${4 \choose 2} = 6$$ $${4 \choose 3} = 4$$ $${4 \choose 4} = 1$$

which can be seen from Table[Binomial[4, k], {k, 1, 4}].

However, I don't just want the number of possible configurations for each k; instead, I want to actually generate the configurations themselves. Is there a simple and elegant -- or perhaps even built-in -- way to do this?

Given an array of size n, generate and print all possible combinations of r elements in array.

Examples:

Input : arr[] = [1, 2, 3, 4],  
            r = 2
Output : [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

This problem has existing recursive solution please refer Print all possible combinations of r elements in a given array of size n link. We will solve this problem in python using itertools.combinations() module.

What does itertools.combinations() do ?

It returns r length subsequences of elements from the input iterable. Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

• itertools.combinations(iterable, r) :
  It return r-length tuples in sorted order with no repeated elements. For Example, combinations(‘ABCD’, 2) ==> [AB, AC, AD, BC, BD, CD].
• itertools.combinations_with_replacement(iterable, r) :
  It return r-length tuples in sorted order with repeated elements. For Example, combinations_with_replacement(‘ABCD’, 2) ==> [AA, AB, AC, AD, BB, BC, BD, CC, CD, DD].

from itertools import combinations

def rSubset(arr, r):

    return list(combinations(arr, r))

if __name__ == "__main__":

    arr = [1, 2, 3, 4]

    r = 2

    print (rSubset(arr, r))

Output:

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

This article is contributed by Shashank Mishra (Gullu). If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.