Skip to content

Instantly share code, notes, and snippets.

@KaleabTessera
Created September 2, 2018 12:48
Show Gist options
  • Save KaleabTessera/6ed2b966637ba56e2252190f7ade1b94 to your computer and use it in GitHub Desktop.
Save KaleabTessera/6ed2b966637ba56e2252190f7ade1b94 to your computer and use it in GitHub Desktop.
This gist contains functions which recursively find all subsets of a set. The min and max subset size can be specified.
import numpy as np
#This function retrieves all subsets in a set recursively.
def findSubsets(allSubsets,subset,currentIndex,maxSubsetSize):
if(len(subset) == currentIndex):
return allSubsets
newSet = []
for i in range(0,len(allSubsets)):
if(len(allSubsets[i]) < maxSubsetSize):
newSet = allSubsets[i].copy()
newSet.append(subset[currentIndex])
allSubsets.append(newSet)
findSubsets(allSubsets, subset, currentIndex+1,maxSubsetSize)
# Find all subsets of a specific size
def findAllSubsetsSpecificSize(array, subsetSize,maxSubsetSize):
allSubsets = [[]]
findSubsets(allSubsets,array,0,maxSubsetSize)
returnSet = []
for sets in allSubsets:
if(len(sets) == subsetSize):
returnSet.append(sets)
return returnSet
#Find all subsets larger than minSubsetSize
def findAllSubsetsWithinRange(array, minSubsetSize,maxSubsetSize):
allSubsets = [[]]
findSubsets(allSubsets,array,0,maxSubsetSize)
returnSet = []
for sets in allSubsets:
if(len(sets) >= minSubsetSize):
returnSet.append(sets)
return returnSet
#Example
allSubsets = [[]]
indexOfSet = []
for i in range(0,28):
indexOfSet.append(i)
minSizeSubset = 3
maxSubsetSize = 7
allSubsets = findAllSubsetsWithinRange(indexOfSet,minSizeSubset,maxSubsetSize)
allSubsetsNumpy = np.array(allSubsets)
print(allSubsetsNumpy)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment