Re: pairs and subsets challenge
- To: mathgroup at smc.vnet.net
- Subject: [mg59214] Re: pairs and subsets challenge
- From: Peter Pein <petsie at dordos.net>
- Date: Tue, 2 Aug 2005 00:42:34 -0400 (EDT)
- References: <dchnkq$7pe$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Daniel Reeves schrieb:
> Here's an interesting problem:
>
> Given a set N = {1,...,n}.
> And given a set P of pairs from N, ie, a subset of KSubsets[N,2].
> List each _maximal_ subset X of N such that KSubsets[X,2] is a
> subset of P.
> Maximal means if X is listed, don't list any subsets of X.
>
> Brute force solutions are not hard to write. This should work for n up to
> 40 and |P| around 500.
>
> Simple example:
>
> N = {1,2,3,4,5};
> P = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{3,5},{4,5}};
>
> output:
>
> {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{3,5},{4,5},
> {3,4,5}, {1,2,3,4}}
>
>
> (no prize this time but I think it'll be fun!)
>
I do not understand the task
" Maximal means if X is listed, don't list any subsets of X."
" output:
{{1,2},... {1,2,3,4}}"
but {1,2} is a subset of {1,2,3,4}
--
Peter Pein
Berlin
http://people.freenet.de/Peter_Berlin/