Re: I Need Help

On Apr 30, 4:05 pm, OwlHoot <ravensd...@xxxxxxxxxxxxxx> wrote:
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,

Looks alone don't make it simple. It's directly executable by
the Jet engine, THAT"S what makes it 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.

Oh? And what takes place "behind the scenes" of a Pascal or C
compiler? Why does the "behind the scenes" activity count for
the Jet engine but not for other implementations?


Also, what if a database is not available?

And what if you don't have a Pascal compiler or a C compiler?
Or have them but don't know how to use them? You're just as
***-outta-luck.

In short, it's nice in principle, but in practice pathetic.

I never said it was the BEST algorithm. That wasn't the question.
And besides, MS-Access can't execute Pascal or C. And even if it
could, you sometimes need such output in a query to link to other
database structures, so the practice isn't nearly as pathetic
as you imagine. Of course, it's intractable if you ask for too much,
but you think a C implementation isn't also intractable if you ask
for all possible 12 letter permutions of 26 letters?


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


Very nice. Still, even the description of the algorithm is longer
then the SQL statement I posted:

Initialize the first permutation with <1 <2 ... <n
while there exists a mobile integer
find the largest mobile integer k
swap k and the adjacent integer it is looking at
reverse the direction of all integers larger than k

let alone the actual implementation (or its behind the scenes
overhead):

(*****************************************************************)
(* Generate permutations by transposing adjacent elements *)
(* via the Steinhaus-Johnson-Trotter algorithm. This is *)
(* the same version used in the book "Combinatorial Generation." *)
(* Both the permutation (in one-line notation) and the positions *)
(* being transposed (as a 2-cycle) are output. *)
(* Programmer: Frank Ruskey *)
(*****************************************************************)

program JohnsonTrotter ( input, output );

var NN, i, count : integer;
p, pi : array [0..100] of integer; {The permutation and its
inverse}
dir : array [0..100] of -1..1; {The directions of each
element}

procedure PrintPerm;
var i : integer;
begin
(* uncomment if you want to print the index of each perm *)
(* count := count + 1;
write( '[',count:8,'] ' );
*)
for i := 1 to NN do write( p[i]:2 );
end {of PrintPerm};

procedure PrintTrans( x, y : integer );
begin
write( ' (',x:0,' ',y:0,')' ); writeln;
end {of PrintTrans};

procedure Move( x, d : integer );
var z : integer;
begin
PrintTrans( pi[x], pi[x]+d );
z := p[pi[x]+d];
p[pi[x]] := z;
p[pi[x]+d] := x;
pi[z] := pi[x];
pi[x] := pi[x]+d;
end {of Move};

procedure Perm ( n : integer );
var i : integer;
begin
if n > NN then PrintPerm
else begin
Perm( n+1 );
for i := 1 to n-1 do begin
Move( n, dir[n] ); Perm( n+1 );
end;
dir[n] := -dir[n];
end;
end {of Perm};

begin
write( 'Enter n: ' ); readln( NN );
writeln;
for i := 1 to NN do begin
dir[i] := -1; p[i] := i; pi[i] := i;
end;
Perm ( 1 );
writeln;
end.

There are loads of online links, as a simple search on those names
and 'permutation' will reveal.

And I have a Python algorithm that does

- permutations with replacement
- combinations with replacement
- permutations without replacement
- combinations without replacement

If I had posted that, you might be justified in claiming there
are "much simpler" ways.

But also I highly recommend the book
I mentioned: "Constructive Combinatorics", by Dennis Stanton
and Dennis White, Springer, 1986.

Fine, if you want to create an implementation in the language of
your choice. SQL is a legitimate language at a much higher level
than C or Pascal, so implementations in those languages will NOT
be "much simpler". Now, there may be implementations in other
languages that are simpler, but you wouldn't know it from the
links you posted.


Cheers

John R Ramsden

Aren't you one of the "good guys"? Clinging to an opinion that's
been shown to be wrong is a trait of what type of personality?

.