List Subsets

[Stian Søiland]

* Simon spake thusly:

> I'm hoping you could show me examples of how a functional/declarative
> language could be used to consicely describe resticted subsets of elements.
> I'm looking for a 'specification' style definition so any ideas/input would
> be very welcome.

> Say I have a list of items which is considered ordered...
> ['iA', 'iB', 'iC', 'iD', 'iE', 'iF']
> (
>   which could also be enumerated if needed...
>   [(0,'iA'), (1,'iB'), (2,'iC'), (3,'iD'), (4,'iE'), (5,'iF')]
> )

> How would I go about writing definitions such that I could calculate...
> a) All ordered subsets.
> e.g:
>  ['iB']
>  ['iA','iD','iE']
>  ['iC','iF']
>  ['iA','iB','iC','iD','iE','iF']

This problem could be solved by thinking of switches for each item. The
complete set of all ordered subsets would then be resolved by iterating
over all possible switch combinations. 

Switches could be considered as bits in a number 'switches' - and
checking if a switch is on (ie. if a element should be included) could
be reduced to checking if a bit is in a number, that is bit-AND of the
item position and the switch number.

The total number of switches for any list of ordered items is 
2** len(items) (each item can be on or off)

Solution:  

(note the zip of range(len(items)) and items to get the
enumerated list you mentioned above)

>>> items = ['iA', 'iB', 'iC', 'iD', 'iE', 'iF']
>>> [[x for (pos,x) in zip(range(len(items)), items) 
...  if (2**pos) & switches] 
...  for switches in range(2**len(items))]

[[],
 ['iA'],
 ['iB'],
 ['iA', 'iB'],
 ['iC'],
 ['iA', 'iC'],
 ['iB', 'iC'],
 ['iA', 'iB', 'iC'],
 ['iD'],
 ['iA', 'iD'],
 ['iB', 'iD'],
 ['iA', 'iB', 'iD'],
 ['iC', 'iD'],
 ['iA', 'iC', 'iD'],
 ['iB', 'iC', 'iD'],
 ['iA', 'iB', 'iC', 'iD'],
 ['iE'],
 ['iA', 'iE'],
 ['iB', 'iE'],
 ['iA', 'iB', 'iE'],
 ['iC', 'iE'],
 ['iA', 'iC', 'iE'],
 ['iB', 'iC', 'iE'],
 ['iA', 'iB', 'iC', 'iE'],
 ['iD', 'iE'],
 ['iA', 'iD', 'iE'],
 ['iB', 'iD', 'iE'],
 ['iA', 'iB', 'iD', 'iE'],
 ['iC', 'iD', 'iE'],
 ['iA', 'iC', 'iD', 'iE'],
 ['iB', 'iC', 'iD', 'iE'],
 ['iA', 'iB', 'iC', 'iD', 'iE'],
 ['iF'],
 ['iA', 'iF'],
 ['iB', 'iF'],
 ['iA', 'iB', 'iF'],
 ['iC', 'iF'],
 ['iA', 'iC', 'iF'],
 ['iB', 'iC', 'iF'],
 ['iA', 'iB', 'iC', 'iF'],
 ['iD', 'iF'],
 ['iA', 'iD', 'iF'],
 ['iB', 'iD', 'iF'],
 ['iA', 'iB', 'iD', 'iF'],
 ['iC', 'iD', 'iF'],
 ['iA', 'iC', 'iD', 'iF'],
 ['iB', 'iC', 'iD', 'iF'],
 ['iA', 'iB', 'iC', 'iD', 'iF'],
 ['iE', 'iF'],
 ['iA', 'iE', 'iF'],
 ['iB', 'iE', 'iF'],
 ['iA', 'iB', 'iE', 'iF'],
 ['iC', 'iE', 'iF'],
 ['iA', 'iC', 'iE', 'iF'],
 ['iB', 'iC', 'iE', 'iF'],
 ['iA', 'iB', 'iC', 'iE', 'iF'],
 ['iD', 'iE', 'iF'],
 ['iA', 'iD', 'iE', 'iF'],
 ['iB', 'iD', 'iE', 'iF'],
 ['iA', 'iB', 'iD', 'iE', 'iF'],
 ['iC', 'iD', 'iE', 'iF'],
 ['iA', 'iC', 'iD', 'iE', 'iF'],
 ['iB', 'iC', 'iD', 'iE', 'iF'],
 ['iA', 'iB', 'iC', 'iD', 'iE', 'iF']]

I don't know if this solution counts as functional or declerative.. with
list comprehensions one could live somewhere inbetween =)


> b) All continuous ordered subset.
> e.g:
>  ['iB']
>  ['iC','iD','iE']
>  ['iE','iF']
>  ['iA','iB','iC','iD','iE','iF']

This could be viewed as different slices(*) of the list. To get all
possible subsets, one needs to iterate over all possible start and stop
positions for the slices.

    (*)  A slice is a 'cutout' of the list, denoted by 
         start and stop positions. Example:

         >>> list = "abcdefgh"
         >>> list[0:3] # three first elements
        'abc'
         >>> list[2:4] # from pos 2 till 4 (not including)
         'cd'

start = 0..len(items)
stop = start..len(items)

This yields a declarative solution:


>>> items
['iA', 'iB', 'iC', 'iD', 'iE', 'iF']
>>> results = []
>>> for start in range(len(items)):
...   for stop in range(start, len(items)):
...     results.append( items[start:stop+1] )

>>> pprint.pprint(results)
[['iA'],
 ['iA', 'iB'],
 ['iA', 'iB', 'iC'],
 ['iA', 'iB', 'iC', 'iD'],
 ['iA', 'iB', 'iC', 'iD', 'iE'],
 ['iA', 'iB', 'iC', 'iD', 'iE', 'iF'],
 ['iB'],
 ['iB', 'iC'],
 ['iB', 'iC', 'iD'],
 ['iB', 'iC', 'iD', 'iE'],
 ['iB', 'iC', 'iD', 'iE', 'iF'],
 ['iC'],
 ['iC', 'iD'],
 ['iC', 'iD', 'iE'],
 ['iC', 'iD', 'iE', 'iF'],
 ['iD'],
 ['iD', 'iE'],
 ['iD', 'iE', 'iF'],
 ['iE'],
 ['iE', 'iF'],
 ['iF']]


> c) All fixed relations, such as 2 items spaced by 2.
> e.g.
>  ['iA','iD']
>  ['iC','iF']

Seems like positional fun again, so this might be best solved 
declarative:

>>> result = []
>>> space = 2+1 # counting the item it self
>>> wantedItems = 2
>>> for start in range(len(items)-space):
...     result.append([items[start+x*space] for x in range(wantedItems)])    

>>> pprint.pprint(result)
[['iA', 'iD'],
 ['iB', 'iE'],
 ['iC', 'iF'],
 ['iA', 'iD'],
 ['iB', 'iE'],
 ['iC', 'iF']]


-- 
Stian Søiland               Being able to break security doesn't make
Trondheim, Norway           you a hacker more than being able to hotwire
http://stain.portveien.to/  cars makes you an automotive engineer. [ESR]