Enumerate_Subsets.mws

---

Enumerating All Subsets of a Set

by Yufang Hao, <yhao@student.math.uwaterloo.ca>

This worksheet enumerates all subsets of a given set and computes the sum of each subset.    

Lists are used instead of sets below, because order of the elements in a set is crucial in order to list all subsets without repetition..

>

restart;

sublist(list,ini)

pre: list is not empty, 1<=ini<=nops(list)
post: sub list containing elements from  ini to nops(list) returns

>	sublist := proc(list, ini)   [ seq(list[i],i=ini..nops(list)) ]: end proc:

>	sublist([a,b,c,d],1);

>	sublist([a,b,c,d],2);

>	sublist([a,b,c,d],4);

addElt(elt,list)

pre: elt is any valid element, and the argument 'list' is a list of lists

post: elt is added at the begining of each element(which is a list) in the argument 'list'.

>	addElt := proc(elt, list)   local templist, i:   templist:=[]:   for i from 1 to nops(list) do     templist:=[ op(templist), [elt, op(list[i])] ]:   end do:   templist: end proc:

>	addElt(m, [[1,a],[2],[3,b,c],[4,d,x,y,x],[]]);

>	addElt(a, [[b,c],[b,d],[c,d]]);

listSubsets(L,i)   

pre: L is a non-empty list, 1<=i<=nops(L)

post: return a list of all possible subsets (sublists) of L with i elements

>

listSubsets := proc(L, i)   local n, j, fl, temp: # fl-final list   n := nops(L):   if i=1 then # base case     fl:=[]:     for j from 1 to n do       fl:=[op(fl),[L[j]]]:     end do:   else     fl:=[]:     for j from 1 to n-i+1 do       temp:=listSubsets(sublist(L,j+1),i-1):       temp:=addElt(L[j],temp):       fl:=[op(fl),op(temp)]:     end do:   end if:   fl: end proc:

>	listSubsets([a,b,c,d,e,f,g],1);

>	listSubsets([a,b,c,d,e,f,g],2);

>	listSubsets([a,b,c,d,e,f,g],4);

listAllSubsets(L)   

pre: L is a non-empty list

post: return a list of all possible subsets (sublists) of L (empty set or null set is excluded)

>	listAllSubsets := proc(L)   local n, i, temp, fl:   n := nops(L):   fl := []:   for i from 1 to n do     fl:=[op(fl),op(listSubsets(L,i))]:   end do:   fl: end proc:

>	listAllSubsets([x,y,z]);

Excluding the empty set, there should be  subsets:

>	nops(listAllSubsets([a,b,c,d,e,f,g,h])) = 2^nops([a,b,c,d,e,f,g,h])-1;

>	listAllSubsets([a,b,c,d,e,f,g,h]);

>

Mathematical Proof and Algorithm

Starting with the following combination formula, we could notice a recursive pattern:

Let (n,i) be the combination of n objects taken i at a time.

then we know (n,i)=(n-1,i-1)+(n-1,i),

and apply this formula again on (n-1,i), we have (n-1,i)=(n-2,i-1)+(n-1,i),

and continue recursively applying this formula, we eventually have:

(n,i) = (n-1,i-1) + (n-2,i-1) + (n-3,i-1) + (n-4,i-1) + ... + (i, i-1) + (i,i)

and (i,i)=1=(i-1,i-1), so (n,i)=(n-1,i-1) + (n-2,i-1) + (n-3,i-1) + (n-4,i-1) + ... + (i, i-1) + (i-1,i-1)

note the sizes of both n and i descrease, so a recrusive formula can be applied.

The algorithm to list all subsets with i elements of L is:

for first element, and combine it with any possible i-1 elements chosen from any element safter first one in L, which is combine with all possible subsets with i-1 elements in the set L(from 2 to n), there are totally (n-1,i-1) ways to select:

1st element + listSubsets(subset(L,2), i-1);

then for second element, combine it with any possible i-1 elements chosen from any elements after second one in L, which is to combine with all possible subsets with i-1 elements in the set L(from 2 to n), there are totally (n-2,i-1) ways to pick:

2nd element + listSubsets(subset(L,3, i-1);

......

for jth element, combine it with any possible i-1 elements chosen from any elements after this jth element in L, which is to combine with all possible subsets with i-1 elements in the set L(from j+1 to n), there are totally (n-j,i-1) ways to pick:

jst element + listSubsets(subset(L,j+1), i-1);

.......

continue until the n-i+1 element is reached, which left only one way (i-1,i-1) way to choose:

And all those combinations form all the possible subsets with i elements of L.

because 'i' decreases by 1 everytime, and 'i' is positive, it eventually reaches 1, which is the base case.

 
  

printAllSubsets(L)   

pre: L is a non-empty list

post: print out all possible subsets (sublists) of L (empty set or null set is excluded)

>	printAllSubsets := proc(L)   local list,i:   list:=listAllSubsets(L):   for i from 1 to nops(list) do     lprint(list[i]):   end do:   return NULL: end proc:

>	printAllSubsets([a,b,c,d]);

[a]

[b]

[c]

[d]

[a, b]

[a, c]

[a, d]

[b, c]

[b, d]

[c, d]

[a, b, c]

[a, b, d]

[a, c, d]

[b, c, d]

[a, b, c, d]

>

printAllSubsetSums(L)   

pre: L is a non-empty list contains number elements

post: print out all possible subsets (sublists) of L (empty set or null set is excluded) and the sum of the numbers in each subset

>	printAllSubsetSums := proc(L)   local list,i,sublist:   list:=listAllSubsets(L):   for i from 1 to nops(list) do     sublist:=list[i]:     lprint( sublist = sum(sublist['k'],'k'=1..nops(sublist)) ):   end do:   return NULL: end proc:

>	printAllSubsetSums([1,2,3,4]);

[1] = 1

[2] = 2

[3] = 3

[4] = 4

[1, 2] = 3

[1, 3] = 4

[1, 4] = 5

[2, 3] = 5

[2, 4] = 6

[3, 4] = 7

[1, 2, 3] = 6

[1, 2, 4] = 7

[1, 3, 4] = 8

[2, 3, 4] = 9

[1, 2, 3, 4] = 10

>	printAllSubsetSums([1,-2,4,-8,16,-32,61,127]);

[1] = 1

[-2] = -2

[4] = 4

[-8] = -8

[16] = 16

[-32] = -32

[61] = 61

[127] = 127

[1, -2] = -1

[1, 4] = 5

[1, -8] = -7

[1, 16] = 17

[1, -32] = -31

[1, 61] = 62

[1, 127] = 128

[-2, 4] = 2

[-2, -8] = -10

[-2, 16] = 14

[-2, -32] = -34

[-2, 61] = 59

[-2, 127] = 125

[4, -8] = -4

[4, 16] = 20

[4, -32] = -28

[4, 61] = 65

[4, 127] = 131

[-8, 16] = 8

[-8, -32] = -40

[-8, 61] = 53

[-8, 127] = 119

[16, -32] = -16

[16, 61] = 77

[16, 127] = 143

[-32, 61] = 29

[-32, 127] = 95

[61, 127] = 188

[1, -2, 4] = 3

[1, -2, -8] = -9

[1, -2, 16] = 15

[1, -2, -32] = -33

[1, -2, 61] = 60

[1, -2, 127] = 126

[1, 4, -8] = -3

[1, 4, 16] = 21

[1, 4, -32] = -27

[1, 4, 61] = 66

[1, 4, 127] = 132

[1, -8, 16] = 9

[1, -8, -32] = -39

[1, -8, 61] = 54

[1, -8, 127] = 120

[1, 16, -32] = -15

[1, 16, 61] = 78

[1, 16, 127] = 144

[1, -32, 61] = 30

[1, -32, 127] = 96

[1, 61, 127] = 189

[-2, 4, -8] = -6

[-2, 4, 16] = 18

[-2, 4, -32] = -30

[-2, 4, 61] = 63

[-2, 4, 127] = 129

[-2, -8, 16] = 6

[-2, -8, -32] = -42

[-2, -8, 61] = 51

[-2, -8, 127] = 117

[-2, 16, -32] = -18

[-2, 16, 61] = 75

[-2, 16, 127] = 141

[-2, -32, 61] = 27

[-2, -32, 127] = 93

[-2, 61, 127] = 186

[4, -8, 16] = 12

[4, -8, -32] = -36

[4, -8, 61] = 57

[4, -8, 127] = 123

[4, 16, -32] = -12

[4, 16, 61] = 81

[4, 16, 127] = 147

[4, -32, 61] = 33

[4, -32, 127] = 99

[4, 61, 127] = 192

[-8, 16, -32] = -24

[-8, 16, 61] = 69

[-8, 16, 127] = 135

[-8, -32, 61] = 21

[-8, -32, 127] = 87

[-8, 61, 127] = 180

[16, -32, 61] = 45

[16, -32, 127] = 111

[16, 61, 127] = 204

[-32, 61, 127] = 156

[1, -2, 4, -8] = -5

[1, -2, 4, 16] = 19

[1, -2, 4, -32] = -29

[1, -2, 4, 61] = 64

[1, -2, 4, 127] = 130

[1, -2, -8, 16] = 7

[1, -2, -8, -32] = -41

[1, -2, -8, 61] = 52

[1, -2, -8, 127] = 118

[1, -2, 16, -32] = -17

[1, -2, 16, 61] = 76

[1, -2, 16, 127] = 142

[1, -2, -32, 61] = 28

[1, -2, -32, 127] = 94

[1, -2, 61, 127] = 187

[1, 4, -8, 16] = 13

[1, 4, -8, -32] = -35

[1, 4, -8, 61] = 58

[1, 4, -8, 127] = 124

[1, 4, 16, -32] = -11

[1, 4, 16, 61] = 82

[1, 4, 16, 127] = 148

[1, 4, -32, 61] = 34

[1, 4, -32, 127] = 100

[1, 4, 61, 127] = 193

[1, -8, 16, -32] = -23

[1, -8, 16, 61] = 70

[1, -8, 16, 127] = 136

[1, -8, -32, 61] = 22

[1, -8, -32, 127] = 88

[1, -8, 61, 127] = 181

[1, 16, -32, 61] = 46

[1, 16, -32, 127] = 112

[1, 16, 61, 127] = 205

[1, -32, 61, 127] = 157

[-2, 4, -8, 16] = 10

[-2, 4, -8, -32] = -38

[-2, 4, -8, 61] = 55

[-2, 4, -8, 127] = 121

[-2, 4, 16, -32] = -14

[-2, 4, 16, 61] = 79

[-2, 4, 16, 127] = 145

[-2, 4, -32, 61] = 31

[-2, 4, -32, 127] = 97

[-2, 4, 61, 127] = 190

[-2, -8, 16, -32] = -26

[-2, -8, 16, 61] = 67

[-2, -8, 16, 127] = 133

[-2, -8, -32, 61] = 19

[-2, -8, -32, 127] = 85

[-2, -8, 61, 127] = 178

[-2, 16, -32, 61] = 43

[-2, 16, -32, 127] = 109

[-2, 16, 61, 127] = 202

[-2, -32, 61, 127] = 154

[4, -8, 16, -32] = -20

[4, -8, 16, 61] = 73

[4, -8, 16, 127] = 139

[4, -8, -32, 61] = 25

[4, -8, -32, 127] = 91

[4, -8, 61, 127] = 184

[4, 16, -32, 61] = 49

[4, 16, -32, 127] = 115

[4, 16, 61, 127] = 208

[4, -32, 61, 127] = 160

[-8, 16, -32, 61] = 37

[-8, 16, -32, 127] = 103

[-8, 16, 61, 127] = 196

[-8, -32, 61, 127] = 148

[16, -32, 61, 127] = 172

[1, -2, 4, -8, 16] = 11

[1, -2, 4, -8, -32] = -37

[1, -2, 4, -8, 61] = 56

[1, -2, 4, -8, 127] = 122

[1, -2, 4, 16, -32] = -13

[1, -2, 4, 16, 61] = 80

[1, -2, 4, 16, 127] = 146

[1, -2, 4, -32, 61] = 32

[1, -2, 4, -32, 127] = 98

[1, -2, 4, 61, 127] = 191

[1, -2, -8, 16, -32] = -25

[1, -2, -8, 16, 61] = 68

[1, -2, -8, 16, 127] = 134

[1, -2, -8, -32, 61] = 20

[1, -2, -8, -32, 127] = 86

[1, -2, -8, 61, 127] = 179

[1, -2, 16, -32, 61] = 44

[1, -2, 16, -32, 127] = 110

[1, -2, 16, 61, 127] = 203

[1, -2, -32, 61, 127] = 155

[1, 4, -8, 16, -32] = -19

[1, 4, -8, 16, 61] = 74

[1, 4, -8, 16, 127] = 140

[1, 4, -8, -32, 61] = 26

[1, 4, -8, -32, 127] = 92

[1, 4, -8, 61, 127] = 185

[1, 4, 16, -32, 61] = 50

[1, 4, 16, -32, 127] = 116

[1, 4, 16, 61, 127] = 209

[1, 4, -32, 61, 127] = 161

[1, -8, 16, -32, 61] = 38

[1, -8, 16, -32, 127] = 104

[1, -8, 16, 61, 127] = 197

[1, -8, -32, 61, 127] = 149

[1, 16, -32, 61, 127] = 173

[-2, 4, -8, 16, -32] = -22

[-2, 4, -8, 16, 61] = 71

[-2, 4, -8, 16, 127] = 137

[-2, 4, -8, -32, 61] = 23

[-2, 4, -8, -32, 127] = 89

[-2, 4, -8, 61, 127] = 182

[-2, 4, 16, -32, 61] = 47

[-2, 4, 16, -32, 127] = 113

[-2, 4, 16, 61, 127] = 206

[-2, 4, -32, 61, 127] = 158

[-2, -8, 16, -32, 61] = 35

[-2, -8, 16, -32, 127] = 101

[-2, -8, 16, 61, 127] = 194

[-2, -8, -32, 61, 127] = 146

[-2, 16, -32, 61, 127] = 170

[4, -8, 16, -32, 61] = 41

[4, -8, 16, -32, 127] = 107

[4, -8, 16, 61, 127] = 200

[4, -8, -32, 61, 127] = 152

[4, 16, -32, 61, 127] = 176

[-8, 16, -32, 61, 127] = 164

[1, -2, 4, -8, 16, -32] = -21

[1, -2, 4, -8, 16, 61] = 72

[1, -2, 4, -8, 16, 127] = 138

[1, -2, 4, -8, -32, 61] = 24

[1, -2, 4, -8, -32, 127] = 90

[1, -2, 4, -8, 61, 127] = 183

[1, -2, 4, 16, -32, 61] = 48

[1, -2, 4, 16, -32, 127] = 114

[1, -2, 4, 16, 61, 127] = 207

[1, -2, 4, -32, 61, 127] = 159

[1, -2, -8, 16, -32, 61] = 36

[1, -2, -8, 16, -32, 127] = 102

[1, -2, -8, 16, 61, 127] = 195

[1, -2, -8, -32, 61, 127] = 147

[1, -2, 16, -32, 61, 127] = 171

[1, 4, -8, 16, -32, 61] = 42

[1, 4, -8, 16, -32, 127] = 108

[1, 4, -8, 16, 61, 127] = 201

[1, 4, -8, -32, 61, 127] = 153

[1, 4, 16, -32, 61, 127] = 177

[1, -8, 16, -32, 61, 127] = 165

[-2, 4, -8, 16, -32, 61] = 39

[-2, 4, -8, 16, -32, 127] = 105

[-2, 4, -8, 16, 61, 127] = 198

[-2, 4, -8, -32, 61, 127] = 150

[-2, 4, 16, -32, 61, 127] = 174

[-2, -8, 16, -32, 61, 127] = 162

[4, -8, 16, -32, 61, 127] = 168

[1, -2, 4, -8, 16, -32, 61] = 40

[1, -2, 4, -8, 16, -32, 127] = 106

[1, -2, 4, -8, 16, 61, 127] = 199

[1, -2, 4, -8, -32, 61, 127] = 151

[1, -2, 4, 16, -32, 61, 127] = 175

[1, -2, -8, 16, -32, 61, 127] = 163

[1, 4, -8, 16, -32, 61, 127] = 169

[-2, 4, -8, 16, -32, 61, 127] = 166

[1, -2, 4, -8, 16, -32, 61, 127] = 167

>	printAllSubsetSums([1,3,7,15,31,63,127]);

[1] = 1

[3] = 3

[7] = 7

[15] = 15

[31] = 31

[63] = 63

[127] = 127

[1, 3] = 4

[1, 7] = 8

[1, 15] = 16

[1, 31] = 32

[1, 63] = 64

[1, 127] = 128

[3, 7] = 10

[3, 15] = 18

[3, 31] = 34

[3, 63] = 66

[3, 127] = 130

[7, 15] = 22

[7, 31] = 38

[7, 63] = 70

[7, 127] = 134

[15, 31] = 46

[15, 63] = 78

[15, 127] = 142

[31, 63] = 94

[31, 127] = 158

[63, 127] = 190

[1, 3, 7] = 11

[1, 3, 15] = 19

[1, 3, 31] = 35

[1, 3, 63] = 67

[1, 3, 127] = 131

[1, 7, 15] = 23

[1, 7, 31] = 39

[1, 7, 63] = 71

[1, 7, 127] = 135

[1, 15, 31] = 47

[1, 15, 63] = 79

[1, 15, 127] = 143

[1, 31, 63] = 95

[1, 31, 127] = 159

[1, 63, 127] = 191

[3, 7, 15] = 25

[3, 7, 31] = 41

[3, 7, 63] = 73

[3, 7, 127] = 137

[3, 15, 31] = 49

[3, 15, 63] = 81

[3, 15, 127] = 145

[3, 31, 63] = 97

[3, 31, 127] = 161

[3, 63, 127] = 193

[7, 15, 31] = 53

[7, 15, 63] = 85

[7, 15, 127] = 149

[7, 31, 63] = 101

[7, 31, 127] = 165

[7, 63, 127] = 197

[15, 31, 63] = 109

[15, 31, 127] = 173

[15, 63, 127] = 205

[31, 63, 127] = 221

[1, 3, 7, 15] = 26

[1, 3, 7, 31] = 42

[1, 3, 7, 63] = 74

[1, 3, 7, 127] = 138

[1, 3, 15, 31] = 50

[1, 3, 15, 63] = 82

[1, 3, 15, 127] = 146

[1, 3, 31, 63] = 98

[1, 3, 31, 127] = 162

[1, 3, 63, 127] = 194

[1, 7, 15, 31] = 54

[1, 7, 15, 63] = 86

[1, 7, 15, 127] = 150

[1, 7, 31, 63] = 102

[1, 7, 31, 127] = 166

[1, 7, 63, 127] = 198

[1, 15, 31, 63] = 110

[1, 15, 31, 127] = 174

[1, 15, 63, 127] = 206

[1, 31, 63, 127] = 222

[3, 7, 15, 31] = 56

[3, 7, 15, 63] = 88

[3, 7, 15, 127] = 152

[3, 7, 31, 63] = 104

[3, 7, 31, 127] = 168

[3, 7, 63, 127] = 200

[3, 15, 31, 63] = 112

[3, 15, 31, 127] = 176

[3, 15, 63, 127] = 208

[3, 31, 63, 127] = 224

[7, 15, 31, 63] = 116

[7, 15, 31, 127] = 180

[7, 15, 63, 127] = 212

[7, 31, 63, 127] = 228

[15, 31, 63, 127] = 236

[1, 3, 7, 15, 31] = 57

[1, 3, 7, 15, 63] = 89

[1, 3, 7, 15, 127] = 153

[1, 3, 7, 31, 63] = 105

[1, 3, 7, 31, 127] = 169

[1, 3, 7, 63, 127] = 201

[1, 3, 15, 31, 63] = 113

[1, 3, 15, 31, 127] = 177

[1, 3, 15, 63, 127] = 209

[1, 3, 31, 63, 127] = 225

[1, 7, 15, 31, 63] = 117

[1, 7, 15, 31, 127] = 181

[1, 7, 15, 63, 127] = 213

[1, 7, 31, 63, 127] = 229

[1, 15, 31, 63, 127] = 237

[3, 7, 15, 31, 63] = 119

[3, 7, 15, 31, 127] = 183

[3, 7, 15, 63, 127] = 215

[3, 7, 31, 63, 127] = 231

[3, 15, 31, 63, 127] = 239

[7, 15, 31, 63, 127] = 243

[1, 3, 7, 15, 31, 63] = 120

[1, 3, 7, 15, 31, 127] = 184

[1, 3, 7, 15, 63, 127] = 216

[1, 3, 7, 31, 63, 127] = 232

[1, 3, 15, 31, 63, 127] = 240

[1, 7, 15, 31, 63, 127] = 244

[3, 7, 15, 31, 63, 127] = 246

[1, 3, 7, 15, 31, 63, 127] = 247

>

>

Summation of the sums of elements in all possible subsets

Let  totalSum be the summation of the sums of the elements in all possible subsets.

getTotalSum(L)   

pre: L is a non-empty list contains number elements

post: return the summation of the sums of elements in all possible subsets

>	getTotalSum := proc(L)   local list,i,sublist,totalsum:   list:=listAllSubsets(L):   totalsum:=0:   for i from 1 to nops(list) do     sublist:=list[i]:     totalsum := totalsum+sum(sublist['k'],'k'=1..nops(sublist)):   end do:   return totalsum: end proc:

>	getTotalSum([1,-2,4,-8,16,-32,61,127]);

>	getTotalSum([1,3,7,15,31,63,127]);

The above procedure finds the totalSum by using loops and recursive functions. An alternative approach is as follows:

For all elements in all possible subsets, their distribution is uniform, (strictly speaking we should use term list, since no repeated elements can be in a set.)  So we only need to find the total number of elements in all possible subsets, then divide by n, and multiply by the sum of the original given list/set.  The same answers should be obtained.

>	getTotalSum2 := proc(L)   local n:   n:=nops(L):   sum(i*binomial(n,i),i=1..n)/n*sum(L[i],i=1..n):   end proc:

>	getTotalSum2([1,-2,4,-8,16,-32,61,127]);

>	getTotalSum2([1,3,7,15,31,63,127]);