Commit034f159

committed

Experiments with using backtracking for generating subsets of n.

1 parent88afcd9 commit034f159Copy full SHA for 034f159

File tree

+62

-0

lines changed

+62

-0

lines changed

Lines changed: 62 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,62 @@`
	`1`	`+"""`
	`2`	`+Generates all subsets`
	`3`	`+"""`
	`4`	`+importsys`
	`5`	`+`
	`6`	`+`
	`7`	`+# def is_solution(k, n):`
	`8`	`+# return k == n`
	`9`	`+#`
	`10`	`+#`
	`11`	`+# def construct_candidates():`
	`12`	`+# return [0, 1]`
	`13`	`+#`
	`14`	`+#`
	`15`	`+# def process_solution(working_set):`
	`16`	`+# global solutions`
	`17`	`+#`
	`18`	`+# s = {k for k in working_set if working_set[k] == 1}`
	`19`	`+# solutions.append(s)`
	`20`	`+#`
	`21`	`+#`
	`22`	`+# def backtrack(working_set, k, n):`
	`23`	`+#`
	`24`	`+# if is_solution(k, n):`
	`25`	`+# process_solution(working_set)`
	`26`	`+# else:`
	`27`	`+# k += 1`
	`28`	`+# candidates = construct_candidates()`
	`29`	`+# for i in candidates:`
	`30`	`+# working_set[k] = i`
	`31`	`+# backtrack(working_set, k, n)`
	`32`	`+`
	`33`	`+`
	`34`	`+defbacktrack_compact(working_set,k,n):`
	`35`	`+globalsolutions`
	`36`	`+`
	`37`	`+ifk==n:`
	`38`	`+s= {kforkinworking_setifworking_set[k]==1}`
	`39`	`+solutions.append(s)`
	`40`	`+else:`
	`41`	`+k+=1`
	`42`	`+foriin [0,1]:`
	`43`	`+working_set[k]=i`
	`44`	`+backtrack_compact(working_set,k,n)`
	`45`	`+`
	`46`	`+`
	`47`	`+defmain():`
	`48`	`+# n = sys.argv[1]`
	`49`	`+n=2`
	`50`	`+`
	`51`	`+globalsolutions`
	`52`	`+solutions= []`
	`53`	`+`
	`54`	`+# backtrack({}, 0, n)`
	`55`	`+# print(solutions)`
	`56`	`+`
	`57`	`+backtrack_compact({},0,n)`
	`58`	`+print(solutions)`
	`59`	`+`
	`60`	`+`
	`61`	`+if__name__=='__main__':`
	`62`	`+main()`

Comments

(0)