permutations/combinations

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
sad69
Forum Newbie
Posts: 3
Joined: Fri Jan 30, 2004 2:35 pm

permutations/combinations

Post by sad69 »

Hi all,

I'm really confused, and have been trying to figure out an algorithm to do the following:

Given an array: [a,b,c,d]
I would like to produce the following array:
[
a,
b,
c,
d,
ab,
ac,
ad,
bc,
bd,
cd,
abc,
abd,
acd,
bcd,
abcd
]

If you can't see the pattern, I'm basically taking all the combinations of the elements of the first array of size 1, size 2, ... size length of that array.

More importantly, the combinations should not repeat eachother since order does not matter. (ie. abc == cab)

The algorithm should work for any length of array.

I've been trying to figure out a recursive algorithm, then an iterative algorithm and I just can't figure it out!

If anyone can help, I'd really appreciate it.

If you have further questions or comments, please let me know. Any and all feedback will help.

Thanks,
Sadiq.
hurrajag
Forum Newbie
Posts: 5
Joined: Wed Feb 04, 2004 10:32 am

Post by hurrajag »

I don't know if this is what you are trying to do but I think you can use numbers (at least you can in C++) in arrays, like
$array[100]; makes an array called "array" with the variables $array[0], $array[1],$array[2] ... $array[98], $array[99]. I don't know if that is what you were asking for, but if it is, I hope it helps... gl anyways.

// HurraJag
sad69
Forum Newbie
Posts: 3
Joined: Fri Jan 30, 2004 2:35 pm

not quite..

Post by sad69 »

That's not at all what I'm looking for.

I've already got an array containing some values (strings). I'd like to create a new array containing the different combinations of those values.

Thanks for your input anyway!

PS. I have thought of an algorithm, a backtracking algorithm that may do it, but I only did it on paper (haven't written any code up yet..).

It's output, given array [a,b,c,d] would be something like:
a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d

I'm pretty swamped with other stuff at work right now, but if no one's come up with a suitable algorithm, I'll see if I can get mine working and I'll post the solution (for any poor souls that have to deal with something like this in the future!).

Thanks again!
Sadiq.
Post Reply