|  | constructing cyclic gray codes | | |
| | | stdazi@gmail.com |  |
|  Posted: Mon Aug 18, 2008 9:13 am Post subject: constructing cyclic gray codes |  |
Hello.
I'm trying to construct all cyclic gray codes of length n.
I've checked the wikipedia article, but I couldn't find a concise
explanation how to do it, so I've simply created a recursive procedure
(python) for the specified task :
===
rez = []
N = 5
def gen_codes(vis, cur_code, remain_code) :
if (remain_code == [] and hamdist(0,cur_code) == 1) : # valid gray
code found
rez.append(vis)
for l in [a for a in remain_code if hamdist(a,cur_code,N) == 1] :
gen_codes(vis + [l] , l, [a for a in remain_code if a != l])
return rez
===
the obvious problem with the code is, that it's way too slow - it's
generating cyclic codes of length 5 for ~18hours.
I'm therefore wondering, if there is any better way to obtain all the
cyclic gray codes of the specified length? Or, at last, a way to
optimize my example?
Thanks,
Jernej. |
| |
| | | Guest | |
| | Posted: Mon Aug 18, 2008 10:48 am Post subject: Re: constructing cyclic gray codes | |
| |  | |
On 18 Aug., 11:13, "std...@gmail.com" <std...@gmail.com> wrote:
| Quote: | Hello.
I'm trying to construct all cyclic gray codes of length n.
I've checked the wikipedia article, but I couldn't find a concise
explanation how to do it, so I've simply created a recursive procedure
(python) for the specified task :
===
rez = []
N = 5
def gen_codes(vis, cur_code, remain_code) :
if (remain_code == [] and hamdist(0,cur_code) == 1) : # valid gray
code found
rez.append(vis)
for l in [a for a in remain_code if hamdist(a,cur_code,N) == 1] :
gen_codes(vis + [l] , l, [a for a in remain_code if a != l])
return rez
===
the obvious problem with the code is, that it's way too slow - it's
generating cyclic codes of length 5 for ~18hours.
|
It can probably speeded up using a compiled language.
A translation of your algorithm to Seed7 is:
===
var array integer: rez is 0 times 0;
var integer: N is 5;
const proc: gen_codes (in array integer: vis,
in integer: cur_code,
in array integer: remain_code) is func
local
var integer: l is 0;
var integer: index is 0;
var array integer: a is 0 times 0;
begin
if length(remain_code) = 0 and hamdist(0, cur_code) = 1 then
# valid gray code found
rez &:= vis;
end if;
for index range minIdx(remain_code) to maxIdx(remain_code) do
l := remain_code[index];
if hamdist(l, cur_code, N) = 1 then
gen_codes(vis & [](l), l, remain_code[.. pred(index)] &
remain_code[succ(index) ..])
end if;
end for;
end func;
===
Some things are missing in your code
- The definition of the hamdist function with two and with
three parameters.
- How the gen_codes function is called to begin the computation.
Because of the missing information I am not able to run my version
of the program.
Greetings Thomas Mertes
Seed7 Homepage: LINK
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows. |
| |
| | | Gene | |
| | Posted: Tue Aug 19, 2008 2:11 am Post subject: Re: constructing cyclic gray codes | |
| | | |
On Aug 18, 5:13 am, "std...@gmail.com" <std...@gmail.com> wrote:
| Quote: | Hello.
I'm trying to construct all cyclic gray codes of length n.
I've checked the wikipedia article, but I couldn't find a concise
explanation how to do it, so I've simply created a recursive procedure
(python) for the specified task :
==> rez = []
N = 5
def gen_codes(vis, cur_code, remain_code) :
if (remain_code == [] and hamdist(0,cur_code) == 1) : # valid gray
code found
rez.append(vis)
for l in [a for a in remain_code if hamdist(a,cur_code,N) == 1] :
gen_codes(vis + [l] , l, [a for a in remain_code if a != l])
return rez
==
the obvious problem with the code is, that it's way too slow - it's
generating cyclic codes of length 5 for ~18hours.
I'm therefore wondering, if there is any better way to obtain all the
cyclic gray codes of the specified length? Or, at last, a way to
optimize my example?
Thanks,
Jernej.
|
Interesting question. I googled "generate all possible gray codes"
and the following came up:
LINK
Looks like others are interested, and recently. |
| |
| | | stdazi@gmail.com | |
| | Posted: Tue Aug 19, 2008 7:48 am Post subject: Re: constructing cyclic gray codes | |
| | | |
This is the best I could do (note, that the above code only enumerates
all the possible cyclic gray codes.)
Sadly, it is only able to compute the relevant values for gray codes
of length 1,2,3,4. (it's stuck computing the respective value for
codes of length 5 for more than two days now)
===========#include <gmp.h>
mpz_t rez ;
static void gnum(unsigned long long curCode, unsigned long long codes,
unsigned n) {
unsigned i;
if (codes == 1 && (curCode & (curCode-1)) == 0) {
mpz_add_ui(rez, rez, 1);
return;
}
for (i = 0 ; i < n; i++)
if ( (1ULL<<(curCode^(1ULL<<i)) & codes ))
gnum(curCode^(1ULL<<i), codes &
~(1ULL<<(curCode^(1ULL<<i)) ), n);
}
int main(void) {
mpz_init(rez);
mpz_set_ui(rez,0);
unsigned i;
for (i = 1 ; i < 6 ; i++) {
mpz_set_ui(rez,0);
gnum(0,(1ULL<< (1<<i) )-1, i);
mpz_div_ui(rez,rez,2);
gmp_printf("Q_%u\t %Zd\n", i, rez);
}
return 0;
}
==========
On Aug 19, 4:11 am, Gene <gene.ress...@gmail.com> wrote:
| Quote: | On Aug 18, 5:13 am, "std...@gmail.com" <std...@gmail.com> wrote:
Hello.
I'm trying to construct all cyclic gray codes of length n.
I've checked the wikipedia article, but I couldn't find a concise
explanation how to do it, so I've simply created a recursive procedure
(python) for the specified task :
==> > rez = []
N = 5
def gen_codes(vis, cur_code, remain_code) :
if (remain_code == [] and hamdist(0,cur_code) == 1) : # valid gray
code found
rez.append(vis)
for l in [a for a in remain_code if hamdist(a,cur_code,N) == 1] :
gen_codes(vis + [l] , l, [a for a in remain_code if a != l])
return rez
==
the obvious problem with the code is, that it's way too slow - it's
generating cyclic codes of length 5 for ~18hours.
I'm therefore wondering, if there is any better way to obtain all the
cyclic gray codes of the specified length? Or, at last, a way to
optimize my example?
Thanks,
Jernej.
Interesting question. I googled "generate all possible gray codes"
and the following came up:
LINK
Looks like others are interested, and recently. |
|
| |
| | | Gene | |
| | Posted: Thu Aug 21, 2008 1:15 am Post subject: Re: constructing cyclic gray codes | |
| | | |
On Aug 18, 5:13 am, "std...@gmail.com" <std...@gmail.com> wrote:
| Quote: | Hello.
I'm trying to construct all cyclic gray codes of length n.
I've checked the wikipedia article, but I couldn't find a concise
explanation how to do it, so I've simply created a recursive procedure
(python) for the specified task :
==> rez = []
N = 5
def gen_codes(vis, cur_code, remain_code) :
if (remain_code == [] and hamdist(0,cur_code) == 1) : # valid gray
code found
rez.append(vis)
for l in [a for a in remain_code if hamdist(a,cur_code,N) == 1] :
gen_codes(vis + [l] , l, [a for a in remain_code if a != l])
return rez
==
the obvious problem with the code is, that it's way too slow - it's
generating cyclic codes of length 5 for ~18hours.
I'm therefore wondering, if there is any better way to obtain all the
cyclic gray codes of the specified length? Or, at last, a way to
optimize my example?
I thought about this a bit. Certainly all the bitwise permutations of |
a gray code are another (different) gray code. Similary all code-wise
rotations of a code are (as far as the algorithm above is concerned)
different. For n=5, the first observation is worth a factor of 120
speedup. The second is a factor of 32. A speedup of 3840 is
probably worthwhile. How to implement? You have to come up with a
canonical form to represent all 3840 equivalent codes as a single
one. The obvious one is to use the first in lexicographical order.
Then build an algorithm that enumerates only canonical forms. When
you find one, generate all 3840 variants at that time.
Example for n=2 we get 2 bit permutation variants and 4 rotational
variants
00 00
01 10
11 11
10 01
01 10
11 11
10 01
00 00
11 11
10 01
00 00
01 10
10 01
00 00
01 10
11 11
The first variant above is canonical. Considered as a "string" of 2-
bit characters it would sort first.
How do you generate only canonical variants? I'll let you work that
out. It's pretty straightforward. |
| |
|
|
