[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

326.0. "Hamiltonian permutation paths" by SPRITE::OSMAN () Thu Aug 01 1985 15:11

A Hamiltonian path through a set of permutations is defined as an ordered
set such that to get from one permutation to the next, you EITHER swap the
last two elements, OR you rotate all the elements left one position,
such that the entire set gets transversed exactly once.

For instance, for the set of three elements, we can start with 123, swap
to produce 132, rotate to produce 321, swap to produce 312 . . . WHOOPS
we're stuck because if we rotate we get 123 which we've already visited,
and if we swap instead, we get 321 which we even more recently visited.

Well, I happen to know that given a few minutes, I could succeed in
finding a Hamiltonian path all the way through the three's (we were only
missing two of the six permutations in that first attempt).

I once wrote a program that fairly easily found a Hamiltonian path through
the four's (i.e. 1234, 1243, 2431, 2413 . . .).  My program never managed
to be efficient enough to prove or disprove that a path exists through
the five's or higher.

Is there a Hamiltonian path through the five's ?  Can anyone prove or
disprove the existence of such paths for any or all other lengths ?
For lengths that have Hamiltonian paths, what's the algorithm for
traversing a path ?  Given the length, how many paths exist ?

/Eric
T.RTitleUserPersonal
Name		DateLines
326.1ADVAX::J_ROTHFri Aug 02 1985 02:319
Though I don't have the reference in my office, I seem to remember the
book 'Combinatorial Algorithms' by Nijenhuis and Wilf discussing this
problem.  This book has quite a collection of neat algorithms
(all in Fortran of all things) and would be worth checking out
even if it doesn't answer your immediate question...  I'm fairly
certain your problem is a well known result of combinatorial theory
though.

- Jim
326.2METOO::YARBROUGHFri Aug 02 1985 09:419
re .1: Nijenhuis and Wilf does not include this particular algorithm - since
it involves rotating an array, it is terribly slow - but does include 
an algorithm in which the only transformations used are exchanges of two 
adjacent elements, which is quite fast. In either algorithm, the difficult
part is the housekeeping: determining which transformation to do next so
that no permutation is repeated. I think I have the N&W algorithm on-line;
if so I will add it this note.

Lynn Yarbrough
326.3ALIEN::POSTPISCHILSun Aug 04 1985 15:12157
A path produced by a program I wrote follows the form-feed.  I think it is
correct, but I have not checked it by hand, yet (you can't trust computers).

I did a few things to speed up the program:

	Actually rotating the elements would take too much time.  Even
	switching them would take a significant amount of time.  So
	the program starts by finding all permutations of five elements
	and gives each of them a number.  Then it fills two arrays.  One
	array gives the number of the permutation found by rotating a
	given permutation; the other arrays gives the number of the
	permutation found by switching the last two elements.

	Another array is maintained as a flag for each permutation,
	indicating whether it has been used or not.  In addition, each
	set of five permutations which can be obtained from each other
	by rotations only is collected:  There is an array which gives
	a set number (from 0 to 23) for each permutation.  An array
	is kept to give the number of used permutations in each set.

	If a set of five permutations is drawn on paper, one can see several
	things:  At most four rotations in a row are possible.  And
	each set of five permutations can support either only four rotations
	or one rotation and two rotations, since a path through all
	the permutations must enter and leave any subset of vertices
	(permutations) and even number of times.

	Thus, if the program performs a switch and finds itself in a set
	of five permutations of which two have already been used, it knows
	it must perform exactly two rotations and a switch.  Conversely,
	finding three permutations used means one rotation and a switch are
	required.  No used permutations means one, two, and four rotations,
	followed by a switch, must all be tried.


				-- edp

Switch.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
Switch.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Switch.
Rotate.
Rotate.
Rotate.
Rotate.
326.4TOOLS::STANThu Aug 08 1985 17:108
I have the following algorithms from Nijenhuis and Wilf typed up:

	NEXPER
	NEXSUB
	PERMAN
	NXTKSB

If anyone wants them, they are in HARE::HACK$:[STAN.MATH]CALG.FOR.
326.5SPRITE::OSMANTue Aug 13 1985 10:189
My original program indeed had the array of indices so that a "rotation"
could be "performed" in very little time.  However, I didn't think of the
stuff about the even number of times through vertices.

So how many paths are there through the 5's ?  (Mr. Postpischel gave one
of them [at least I think it was him, and I think I spelled it right, I
haven't yet figured out how to read random previous replies while in the
middle of typing a reply to a note, other than spawning or using reply/last])
326.6ALIEN::POSTPISCHILFri Aug 16 1985 10:487
A version of the program used to find the previously entered path says there
are 252 paths.  This includes rotations of paths.  That is, a path without
rotational symmetry has been counted 120 times.  A path which can and must be
rotated by 60 elements to get the same path has been counted 60 times.


				-- edp
326.7R2ME2::GILBERTFri Aug 16 1985 18:183
Could the program be modified to search for a Hamiltonian path through
the set of permutations of six elements?  Seven?  If not, this would
disprove the theorem.
326.8ALIEN::POSTPISCHILFri Aug 16 1985 18:3718
Re .7:

> Could the program be modified to search for a Hamiltonian path through
> the set of permutations of six elements?  Seven?  If not, this would
> disprove the theorem.

I do not understand the connection here.  Being not modifiable might simply
have something to do with the program, not the existence of paths.  Being
modifiable might merely lead to a search that fails.

As it happens, the program is modifiable.  Only a few constants at the
beginning of the code and an initialization routine need to be changed.  But
the search for a path with 120 elements took around two CPU-minutes (on ALIEN,
which is a VAX-11/780).  How long would a search for a path with 720 elements
take?


				-- edp
326.9ALIEN::POSTPISCHILSat Aug 17 1985 12:206
To correct my earlier statement, there are 252 paths, where each rotation of a
path that begins with a switch operation is counted.  I should have the number
of paths, excluding rotations, soon. 


				-- edp
326.10ALIEN::POSTPISCHILMon Aug 19 1985 09:346
Okay, here we are:  There are nine paths through the fives.

.0 claims there is a path through the fours.  I disagree.  Any objections?


				-- edp
326.11ALIEN::POSTPISCHILWed Aug 21 1985 11:254
Can anyone confirm or deny there are no paths through the fours?


				-- edp
326.12SPRITE::OSMANWed Aug 28 1985 12:23241
I claim there is at least one Hamiltonian path through the fours.  Here it
is:

Hamiltonian path through permutations of four objects:
0123 rotate . . .
1230 rotate . . .
2301 rotate . . .
3012 swap . . .
3021 rotate . . .
0213 rotate . . .
2130 swap . . .
2103 rotate . . .
1032 swap . . .
1023 rotate . . .
0231 rotate . . .
2310 rotate . . .
3102 swap . . .
3120 rotate . . .
1203 rotate . . .
2031 rotate . . .
0312 swap . . .
0321 rotate . . .
3210 swap . . .
3201 rotate . . .
2013 rotate . . .
0132 rotate . . .
1320 swap . . .
1302

That path was produced with the following BLISS program.  If you want
to run it as is, you'll also need SPRITE::USER1:[OSMAN.BLISSLIB]USEFULBLI.L32
and TERMNL.OBJ.  Here's the program:

module hamil (main = beg, addressing_mode (external = general, nonexternal =
general)) = begin

forward routine!s

	beg,
	hamil,
	slow_rotate,
	slow_swap,
	index_to_digits,
	digits_to_index,
	printout;

library 'sys$library:starlet';
library 'blisslib:usefulbli';

literal

	c_indicate_swap = 0, c_indicate_rotate = 1,
	max_n_factorial = 24;

own

	n : initial (4),
	n_factorial : initial (24),
	seen : vector [max_n_factorial],
	path : vector [max_n_factorial],
	rotate_table : vector [max_n_factorial],
	op : vector [max_n_factorial],
	swap_table : vector [max_n_factorial];


routine printout =

	begin

	local

	    digits : vector [4];

	type ('Hamiltonian path through permutations of four objects:');

	incr i from 0 to .n_factorial - 1 do
	    begin
	    index_to_digits (.path[.i], digits[0]);
	    typePart (decimal (.digits[0]), decimal (.digits[1]),
		decimal (.digits[2]), decimal (.digits[3]));
	    if .i neq .n_factorial - 1
	    then
		selectOne .op[.i + 1] of set
		[c_indicate_rotate] : typePart (' rotate . . .');
		[c_indicate_swap]   : typePart (' swap . . .');
		tes;
	    typeCarriageReturn ()
	    end

	end;

routine beg =

	begin

	ch$fill (0, 4 * .n_factorial, seen[0]);

	incr i from 0 to .n_factorial - 1 do
	    begin
	    rotate_table[.i] = slow_rotate(.i);
	    swap_table[.i] = slow_swap(.i)
	    end;

	seen[0] = 1;
	path[0] = 0;

	if hamil (1)
	then printout ()
	else type ('No hamiltonian paths found through the permutations of ',
	    decimal (.n), ' objects.');

	ss$_normal

	end;

routine hamil (current) =

	begin

	local

	    state : initial (.path[.current - 1]);

	if .current geq .n_factorial
	then return 1;

	if not .seen[.rotate_table[.state]]
	then
	    begin
	    path[.current] = .rotate_table[.state];
	    seen[.rotate_table[.state]] = 1;
	    op[.current] = c_indicate_rotate;
	    if hamil (.current + 1)
	    then return 1;
	    seen[.rotate_table[.state]] = 0
	    end;

	if not .seen[.swap_table[.state]]
	then
	    begin
	    path[.current] = .swap_table[.state];
	    seen[.swap_table[.state]] = 1;
	    op[.current] = c_indicate_swap;
	    if hamil (.current + 1)
	    then return 1;
	    seen[.swap_table[.state]] = 0
	    end;

	return 0

	end;

routine slow_rotate (index) =

	begin

	local

	    digits : vector [4], temp;

	index_to_digits (.index, digits[0]);

	temp = .digits[0];
	digits[0] = .digits[1];
	digits[1] = .digits[2];
	digits[2] = .digits[3];
	digits[3] = .temp;

	digits_to_index (digits[0])

	end;

routine slow_swap (index) =

	begin

	local

	    digits : vector [4], temp;

	index_to_digits (.index, digits[0]);

	temp = .digits[2];
	digits[2] = .digits[3];
	digits[3] = .temp;

	digits_to_index (digits[0])

	end;

routine digits_to_index (digits : ref vector [4]) =

	begin

	local

	    index : initial ((((.digits[0] * 10) + .digits[1]) * 10 +
		.digits[2]) * 10 + .digits[3]),

	    codes : vector [24] initial (
		0123, 0132, 0213, 0231, 0312, 0321,
		1023, 1032, 1203, 1230, 1302, 1320,
		2013, 2031, 2103, 2130, 2301, 2310,
		3012, 3021, 3102, 3120, 3201, 3210);

	(ch$find_sub (24 * 4, codes[0], 4, index) - codes[0]) / 4

	end;

routine index_to_digits (index, digits : ref vector[4]) =

	begin

	local

	    choice;

	macro rest (a,b,c,d,e,f) =
	    choice = (case .index mod 6 from 0 to 5 of set
		[0]:a;[1]:b;[2]:c;[3]:d;[4]:e;[5]:f;tes) % ;

	digits[0] = .index / 6;

	case .digits[0] from 0 to 3 of set
	[0] : rest (123, 132, 213, 231, 312, 321);
	[1] : rest (023, 032, 203, 230, 302, 320);
	[2] : rest (013, 031, 103, 130, 301, 310);
	[3] : rest (012, 021, 102, 120, 201, 210);
	tes;

	digits[3] = .choice mod 10;
	digits[2] = .choice / 10;
	digits[1] = .digits[2] / 10;
	digits[2] = .digits[2] mod 10

	end;

end
eludom

/Eric
326.13ALIEN::POSTPISCHILWed Aug 28 1985 14:015
I assumed the paths should be closed.  All of my results to date use that
assumption.


				-- edp