Re: I Need Help

On Apr 30, 8:10 pm, "mensana...@xxxxxxxxxxx" <mensana...@xxxxxxx>
wrote:
On Apr 30, 3:33 am, OwlHoot <ravensd...@xxxxxxxxxxxxxx> wrote:

On Apr 30, 4:03 am, "mensana...@xxxxxxxxxxx" <mensana...@xxxxxxx>
wrote:

On Apr 29, 5:17?pm, aelha...@xxxxxxxxx wrote:

I Need Some Algorithm To finding all possible combinations of M
different symbols
like A B C

A A B B C C
B C A C A B
C B C A B A

Start an Access database. Make a table and put in it
each symbol as a record (three records in this example).
Now make a query and put in it as many copies of the
table as there are places in the output (six in the example
given).

Make sure you don't link any of the tables!

Run the query and the database will create the Cartesian
Product of the 6 tables copies.

Voila.

There's a much simpler way than that.

Really?

It's explained in
"Constructive Combinatorics" by Stanton.

If no one else explains it, I'll dig out my copy and post
a summary.

Summary? I thought you said it was much simpler?

How much simpler can you get than

SELECT T_5.c, T_4.c, T_3.c, T_2.c, T_1.c, T.c
FROM T, T AS T_1, T AS T_2, T AS T_3, T AS T_4, T AS T_5;

That may look simple, but behind the scenes there's a hell of a lot
going on and, quite possibly, huge amounts of memory being used
for temp tables and so forth.

Also, what if a database is not available? In short, it's nice in
principle, but in practice pathetic.

I dug out the reference I quoted, and the algorithm it mentions is
called the [Steinhaus-]Johnson-Trotter algorithm. See:

* http://en.wikipedia.org/wiki/Steinhaus-Johnson-Trotter_algorithm

* http://www.nist.gov/dads/HTML/johnsonTrotter.html

There are loads of online links, as a simple search on those names
and 'permutation' will reveal. But also I highly recommend the book
I mentioned: "Constructive Combinatorics", by Dennis Stanton
and Dennis White, Springer, 1986.


Cheers

John R Ramsden

.