Permutations algoritm?

[Manuel M. Garcia]

On Fri, 15 Nov 2002 15:51:04 -0600, sismex01 at hebmex.com wrote:
(edit)
>Of a set of different items 'S', obtain all distinct subsets of 'n'
>items where all items in the subset are different.
>
>So, if I have, for example:
>
>   S = [ 0, 1, 2, 3 ]
>
>the universe of available subsets of 3 items would be:
>
>   s = [ (0, 1, 2),
>         (0, 1, 3),
>         (0, 2, 3),
>         (1, 2, 3) ]
>
>the universe of available subsets of 2 items would be:
>
>   s = [ (0, 1),
>         (0, 2),
>         (0, 3),
>         (1, 2),
>         (1, 3),
>         (2, 3) ]

import pprint

def _subsets_ofsize_help(n, m):
    if m == 0:
        return [ [] ]
    elif n == 0:
        return []
    elif m == 1:
        return [ [i] for i in range(n) ]
    else:
        s0 = _subsets_ofsize_help(n-1,m)
        s1 = _subsets_ofsize_help(n-1,m-1)
        for i in range(len(s1)):
            s1[i].append(n-1)
        s0.extend(s1)
        return s0

def _subsets_help(n):
    s = [ [] ]
    if n == 0: return s
    for i in range(n):
        s0 = _subsets_ofsize_help(n,i+1)
        s0.sort()
        s.extend(s0)
    return s

def DistinctSubsets(set):
    return [ tuple([set[i] for i in s])
             for s in _subsets_help(len(set)) ]

pprint.pprint(
    DistinctSubsets(
        ('Sunday',
         'Monday',
         'Tuesday',
         'Wednesday',
         'Thursday')) )

----Output-----

[(),
 ('Sunday',),
 ('Monday',),
 ('Tuesday',),
 ('Wednesday',),
 ('Thursday',),
 ('Sunday', 'Monday'),
 ('Sunday', 'Tuesday'),
 ('Sunday', 'Wednesday'),
 ('Sunday', 'Thursday'),
 ('Monday', 'Tuesday'),
 ('Monday', 'Wednesday'),
 ('Monday', 'Thursday'),
 ('Tuesday', 'Wednesday'),
 ('Tuesday', 'Thursday'),
 ('Wednesday', 'Thursday'),
 ('Sunday', 'Monday', 'Tuesday'),
 ('Sunday', 'Monday', 'Wednesday'),
 ('Sunday', 'Monday', 'Thursday'),
 ('Sunday', 'Tuesday', 'Wednesday'),
 ('Sunday', 'Tuesday', 'Thursday'),
 ('Sunday', 'Wednesday', 'Thursday'),
 ('Monday', 'Tuesday', 'Wednesday'),
 ('Monday', 'Tuesday', 'Thursday'),
 ('Monday', 'Wednesday', 'Thursday'),
 ('Tuesday', 'Wednesday', 'Thursday'),
 ('Sunday', 'Monday', 'Tuesday', 'Wednesday'),
 ('Sunday', 'Monday', 'Tuesday', 'Thursday'),
 ('Sunday', 'Monday', 'Wednesday', 'Thursday'),
 ('Sunday', 'Tuesday', 'Wednesday', 'Thursday'),
 ('Monday', 'Tuesday', 'Wednesday', 'Thursday'),
 ('Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday')]

Manuel