List Subsets

**Bengt Richter** · Jul 18 '05, 05:43 AM

Re: List Subsets

On Tue, 18 Nov 2003 22:15:25 +0000 (UTC), "Simon" <sorrynomail@no .no> wrote:
[color=blue]
>Hi,
>
>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.
>
>Thanks for your time,
>Simon.
>--
>Say I have a list of items which is considered ordered...
>[/color]
[...]
sounds like homework ;-)

Regards,
Bengt Richter

**Simon** · Jul 18 '05, 05:46 AM

Re: List Subsets

> >I'm hoping you could show me examples of how a functional/declarative[color=blue][color=green]
> >language could be used to consicely describe resticted subsets of[/color][/color]
elements.[color=blue][color=green]
> >I'm looking for a 'specification' style definition so any ideas/input[/color][/color]
would[color=blue][color=green]
> >be very welcome.
> >--
> >Say I have a list of items which is considered ordered...
> >[/color]
> [...]
> sounds like homework ;-)[/color]

If you mean I am doing my homework, then yes! My job doesn't demand that I
go and look at this kind of stuff but I do because it is interesting and
brings new ideas to the table. I was trying to give example scenarios
because I thought it made it easier to address, but it seems that implies I
am a lazy student!

I can't learn every languae under the sun to see if it is interesting to my
goals, but what I can do is ask for the advice of experts in languages that
could be interesting to decide which ones are worth spending the time over
to learn for the types of problem i'm trying to address. I hope this seems
reasonable.

As stated before, I'm looking for a 'specification' style definition of my
original problem, so any ideas/input would be very welcome.

Thanks again,
Simon.

**Stian Søiland** · Jul 18 '05, 05:57 AM

Re: List Subsets

* Simon spake thusly:
[color=blue]
> 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.[/color]
[color=blue]
> 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')]
> )[/color]
[color=blue]
> 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'][/color]

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)
[color=blue][color=green][color=darkred]
>>> items = ['iA', 'iB', 'iC', 'iD', 'iE', 'iF']
>>> [[x for (pos,x) in zip(range(len(i tems)), items)[/color][/color][/color]
.... if (2**pos) & switches]
.... for switches in range(2**len(it ems))]

[[],
['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 =)

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

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:
[color=blue][color=green][color=darkred]
>>> list = "abcdefgh"
>>> list[0:3] # three first elements[/color][/color][/color]
'abc'[color=blue][color=green][color=darkred]
>>> list[2:4] # from pos 2 till 4 (not including)[/color][/color][/color]
'cd'

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

This yields a declarative solution:

[color=blue][color=green][color=darkred]
>>> items[/color][/color][/color]
['iA', 'iB', 'iC', 'iD', 'iE', 'iF'][color=blue][color=green][color=darkred]
>>> results = []
>>> for start in range(len(items )):[/color][/color][/color]
.... for stop in range(start, len(items)):
.... results.append( items[start:stop+1] )
[color=blue][color=green][color=darkred]
>>> pprint.pprint(r esults)[/color][/color][/color]
[['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']]

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

Seems like positional fun again, so this might be best solved
declarative:
[color=blue][color=green][color=darkred]
>>> result = []
>>> space = 2+1 # counting the item it self
>>> wantedItems = 2
>>> for start in range(len(items )-space):[/color][/color][/color]
.... result.append([items[start+x*space] for x in range(wantedIte ms)])
[color=blue][color=green][color=darkred]
>>> pprint.pprint(r esult)[/color][/color][/color]
[['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]

List Subsets

List Subsets

Comment

Comment

Comment