This example uses a recursive algorithm to generate selections of K items from a set of N items. For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Generate all the selections of K items from a set of N items in Python

[This example generates all the selections of K items from a set of N items in Python.]

The basic idea is to start with an empty combination and then use a recursive method to assign the next item to the growing combination. The first call to the method assigns the combination's first item, the next call assigns the second item, and so forth until the combination is complete. To assign an item, the method loops through all of the objects looking for those that have not already been assigned. When it finds such an item, the method:

Marks the item as used in the current permutation
Recursively calls itself to assign the next item in the current permutation

When the recursive call returns, the method unmarks the item so it is not used and can be used again later in future combinations.

The recursion continues until the combination contains the right number of items. Then the method reads the items that are selected in the current combination and adds them to the list of results.

The following generate_selections method basically sets up and then calls the select_items method (described later) to do the real work.

def generate_selections(items, n): '''Generate selections of n items.''' # Make a list to tell whether an item is in the current selection. in_selection = [False for i in range(len(items))] # Make a result list. results = [] # Build the combinations recursively. select_items(items, in_selection, results, n, 0) # Return the results. return results

This method first makes a list called in_selection to indicate which items are in the current selection. Initially the selection is empty so this list contains all False entries.

Next the code makes an empty results list and calls selected_items to do the fun part. It then returns the results that were built by the selected_items method. The following code shows that method.

def select_items(items, in_selection, results, n, first_item): ''' Recursively select n additional items with indexes >= first_item. If n == 0, add the current combination to the results. ''' if n == 0: # Add the current selection to the results. selection = [] for i in range(len(items)): # If this item is selected, add it to the selection. if in_selection[i]: selection.append(items[i]) results.append(selection) else: # Try adding each of the remaining items. for i in range(first_item, len(items)): # Try adding this item. in_selection[i] = True # Recursively add the rest of the required items. select_items(items, in_selection, results, n - 1, i + 1) # Remove this item from the selection. in_selection[i] = False

This function's parameters are:

items: The list of items from which to select
in_selection: The list indicating which items are in the current selection
results: The list holding complete selections
n: The number of items that we still need to add to make a complete selection
first_item: The index of the first item that we should consider for adding

This function checks n. If n is 0, we have a complete assignment. In that case, the program makes an empty selection list and loops through is_selection to see which items are included. If in_selection[i] is True, the code appends items[i] to the selection. After it has built the selection, the method appends it to the results list.

If n is greater than 0, we don't have a complete selection yet. In that case, the function loops through the items that are still up for consideration and tries adding each. For each item, it sets the item's in_selection value to True and then recursively calls itself to pick the rest of the items. After the recursive call returns, the function resets the item's in_selection value to False to indicate that it is not in the selection.

Note that this method may "waste" some function calls. For example, if we're picking 5 items, have only selected 2, and there are only 2 items left to consider, then we won't be able to make a full selection even if we add both of the remaining items to the selection. There are only a few such calls, relatively speaking, so we just ignore them.

The following code uses the generate_selections method to pick 3 of 5 animals and then 4 of 7 numbers.

import math items = ['Ant', 'Bat', 'Cat', 'Dog', 'Eel'] k = 3 result = generate_selections(items, k) assert len(result) == math.comb(len(items), k) print(f'{len(result)} selections') for selection in result: print(selection) print()

math.comb

math.comb(n, k)

n

K

generate_selections

Download the example to see all of the details.