Hello,
i need a function, that build all combinations
(ok - not realy ALL combinations)
What i need is:
(all-combis '(1 2 3 4))
>> ((1) (2) (3) (4) (1 2) (1 3) (2 3) (2 4)
(3 4) (1 2 3 (2 3 4) (1 2 4) (1 3 4) (1 2 3 4))
ok - if you can help me - please do it
In article <···························@posting.google.com>,
frank <···············@yahoo.de> wrote:
>Hello,
>
>i need a function, that build all combinations
>(ok - not realy ALL combinations)
>
>What i need is:
>
>(all-combis '(1 2 3 4))
>
>>> ((1) (2) (3) (4) (1 2) (1 3) (2 3) (2 4)
>(3 4) (1 2 3 (2 3 4) (1 2 4) (1 3 4) (1 2 3 4))
>
>ok - if you can help me - please do it
Sounds like homework, so it would be better if you did it yourself.
If you're having trouble getting it working, post what you have and we can
advise. But we won't just do it for you.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <····························@posting.google.com>, frank wrote:
> Barry Margolin <······@genuity.net> wrote in message news:<·················@paloalto-snr1.gtei.net>...
>> In article <···························@posting.google.com>,
>> frank <···············@yahoo.de> wrote:
>> >Hello,
>> >
>> >i need a function, that build all combinations
>> >(ok - not realy ALL combinations)
>> >
>> >What i need is:
>> >
>> >(all-combis '(1 2 3 4))
>> >
>> >>> ((1) (2) (3) (4) (1 2) (1 3) (2 3) (2 4)
>> >(3 4) (1 2 3 (2 3 4) (1 2 4) (1 3 4) (1 2 3 4))
>> >
>> >ok - if you can help me - please do it
>>
>> Sounds like homework, so it would be better if you did it yourself.
>>
>> If you're having trouble getting it working, post what you have and we can
>> advise. But we won't just do it for you.
>
> yes - i really want to do it by myself
>
> ok - the only idear, that i have is
[snip]
The name the resulting list of lists is the "power set". Searching for
power set algorithms may give you ideas about a more efficient
implementation. The power set can be produced with a pretty concise
recursive algorithm.
Zach
--
Zachary Beane ····@xach.com
Do it eXtreme Programming style:
First write a function that returns all combinations
of just ONE item, this should be real easy ;-)
Then re-write the function to return all combinations
of TWO items, this will be a little harder.
Then re-write the function to return all combinations
of THREE items, you will probably be done by this point.
Try your function with FOUR items and fix if necessary.
frank wrote:
> i need a function, that build all combinations
> (all-combis '(1 2 3 4))
> >> ((1) (2) (3) (4) (1 2) (1 3) (1 4) (2 3) (2 4)
> (3 4) (1 2 3) (2 3 4) (1 2 4) (1 3 4) (1 2 3 4))
#:(all-combis '(1))
((1))
#:(all-combis '(1 2))
((1) (2) (1 2))
#:(all-combis '(1 2 3))
Thanks,
Jeff Sandys
((1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))
···············@yahoo.de (frank) writes:
> i need a function, that build all combinations
> (ok - not realy ALL combinations)
>
> What i need is:
>
> (all-combis '(1 2 3 4))
>
> >> ((1) (2) (3) (4) (1 2) (1 3) (2 3) (2 4)
> (3 4) (1 2 3 (2 3 4) (1 2 4) (1 3 4) (1 2 3 4))
Here's an approach I took for a comparable problem, starting with a
list L of length N:
Create a bit vector V of length N.
For each value from 0 to 2^N in V,
Collect the following:
For each of the "on" bits in V,
Collect the elements in the corresponding positions in L.
This isn't the more common recursive solution, but I had to run tests
to decide whether to generate a set or not, hence the difference.
--
Rob St. Amant
http://www4.ncsu.edu/~stamant
Helu
* ·······@haeckel.csc.ncsu.edu (Robert St. Amant) writes:
| Here's an approach I took for a comparable problem, starting with a
| list L of length N:
|
| Create a bit vector V of length N.
| For each value from 0 to 2^N in V,
| Collect the following:
| For each of the "on" bits in V,
| Collect the elements in the corresponding positions in L.
|
| This isn't the more common recursive solution, but I had to run tests
| to decide whether to generate a set or not, hence the difference.
If you cared about the order in which the sets are generated, we can
compute V iteratively as: (just pseudocode here)
loop with cardinality = 0 ;; cardinality of current subset
for m from 1
for j = largest power of 2 which divides m
while (cardinality /= 1) or the last bit of V is still 0
flip the jth bit in V
cardinality = cardinality + 2 * V[j] - 1
;; collect the sets corresponding to the on bits in V
|
| --
| Rob St. Amant
| http://www4.ncsu.edu/~stamant
Regards
Madhu
--
Open system or closed system, enlightenment or ideology, those are the
questions. "John C. Mallery" <····@ai.mit>
Madhu <···················@cs.unm.edu> writes:
> Helu
>
> * ·······@haeckel.csc.ncsu.edu (Robert St. Amant) writes:
>
> | Here's an approach I took for a comparable problem, starting with a
> | list L of length N:
> |
> | Create a bit vector V of length N.
> | For each value from 0 to 2^N in V,
> | Collect the following:
> | For each of the "on" bits in V,
> | Collect the elements in the corresponding positions in L.
> |
> | This isn't the more common recursive solution, but I had to run tests
> | to decide whether to generate a set or not, hence the difference.
>
> If you cared about the order in which the sets are generated, we can
> compute V iteratively as: (just pseudocode here)
>
> loop with cardinality = 0 ;; cardinality of current subset
> for m from 1
> for j = largest power of 2 which divides m
> while (cardinality /= 1) or the last bit of V is still 0
> flip the jth bit in V
> cardinality = cardinality + 2 * V[j] - 1
> ;; collect the sets corresponding to the on bits in V
Cool. Thanks, I'll store this away.
--
Rob St. Amant
http://www4.ncsu.edu/~stamant
From: Vassil Nikolov
Subject: Re: a function like all-combinations
Date:
Message-ID: <uvg4a51fx.fsf@poboxes.com>
On 09 Oct 2002 17:30:29 -0400, ·······@haeckel.csc.ncsu.edu (Robert St. Amant) said:
[...]
RSA> Create a bit vector V of length N.
RSA> For each value from 0 to 2^N in V,
I'm curious how you step the value---or is that an integer V,
considered as a string of bits?
---Vassil.
--
Non-googlable is googlable.
Vassil Nikolov <········@poboxes.com> writes:
> On 09 Oct 2002 17:30:29 -0400, ·······@haeckel.csc.ncsu.edu (Robert St. Amant) said:
>
> [...]
> RSA> Create a bit vector V of length N.
> RSA> For each value from 0 to 2^N in V,
>
> I'm curious how you step the value---or is that an integer V,
> considered as a string of bits?
Yes, it's an integer. I was trying simultaneously to avoid giving
code and to make the idea clear; there are calls to logbitp and
related functions sprinkled through the form. I should probably have
given more thought to efficiency, but oh well. . .
--
Rob St. Amant
http://www4.ncsu.edu/~stamant
In article <···············@haeckel.csc.ncsu.edu>,
Robert St. Amant <·······@haeckel.csc.ncsu.edu> wrote:
>Vassil Nikolov <········@poboxes.com> writes:
>
>> On 09 Oct 2002 17:30:29 -0400, ·······@haeckel.csc.ncsu.edu (Robert
>St. Amant) said:
>>
>> [...]
>> RSA> Create a bit vector V of length N.
>> RSA> For each value from 0 to 2^N in V,
>>
>> I'm curious how you step the value---or is that an integer V,
>> considered as a string of bits?
>
>Yes, it's an integer. I was trying simultaneously to avoid giving
>code and to make the idea clear; there are calls to logbitp and
>related functions sprinkled through the form. I should probably have
>given more thought to efficiency, but oh well. . .
It was confusing because you said "bit vector", which is a distinct type in
Common Lisp, *not* the same as using the bit operations on an integer.
We probably should have provided a built-in operation to convert between
integers and bit vectors (and perhaps other vectors of fixed-size
integers). It's not too difficult to roll these yourself, but it seems
like a frequent need and the implementation can probably do it more
efficiently by copying the representation in one fell swoop.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <······@genuity.net> writes:
> In article <···············@haeckel.csc.ncsu.edu>,
> Robert St. Amant <·······@haeckel.csc.ncsu.edu> wrote:
> >Vassil Nikolov <········@poboxes.com> writes:
> >
> >> On 09 Oct 2002 17:30:29 -0400, ·······@haeckel.csc.ncsu.edu (Robert
> >St. Amant) said:
> >>
> >> [...]
> >> RSA> Create a bit vector V of length N.
> >> RSA> For each value from 0 to 2^N in V,
> >>
> >> I'm curious how you step the value---or is that an integer V,
> >> considered as a string of bits?
> >
> >Yes, it's an integer. I was trying simultaneously to avoid giving
> >code and to make the idea clear; there are calls to logbitp and
> >related functions sprinkled through the form. I should probably have
> >given more thought to efficiency, but oh well. . .
>
> It was confusing because you said "bit vector", which is a distinct type in
> Common Lisp, *not* the same as using the bit operations on an integer.
Yes, that was a dumb mistake on my part for describing it that way.
> We probably should have provided a built-in operation to convert between
> integers and bit vectors (and perhaps other vectors of fixed-size
> integers). It's not too difficult to roll these yourself, but it seems
> like a frequent need and the implementation can probably do it more
> efficiently by copying the representation in one fell swoop.
I think that this has come up before on comp.lang.lisp; I agree, for
some things it would be pretty handy to have these as primitives. For
example, I found it helpful to write a set-logbit function that called
logior and logandc2, just to have the abstraction.
--
Rob St. Amant
http://www4.ncsu.edu/~stamant
In article <···············@haeckel.csc.ncsu.edu>,
Robert St. Amant <·······@haeckel.csc.ncsu.edu> wrote:
>I think that this has come up before on comp.lang.lisp; I agree, for
>some things it would be pretty handy to have these as primitives. For
>example, I found it helpful to write a set-logbit function that called
>logior and logandc2, just to have the abstraction.
Isn't that what DPB is for?
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <······@genuity.net> writes:
> In article <···············@haeckel.csc.ncsu.edu>,
> Robert St. Amant <·······@haeckel.csc.ncsu.edu> wrote:
> >I think that this has come up before on comp.lang.lisp; I agree, for
> >some things it would be pretty handy to have these as primitives. For
> >example, I found it helpful to write a set-logbit function that called
> >logior and logandc2, just to have the abstraction.
>
> Isn't that what DPB is for?
Live and learn. Thanks!
--
Rob St. Amant
http://www4.ncsu.edu/~stamant