Created
September 2, 2018 12:48
-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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