## Permutations

Requests, not necessarily related to fpga4fun...

### Permutations

Hello all,

I am trying to list all permutations, for example I have 'a', 'b' and 'c'. We will assume these are ascii using 8 bits each.

I have a wire defined [0:23] that could hold the 3 ascii bytes.
Now the simple (very hard) bit, using verilog if possible how would I go about changing the wire to contain each permutation?

I understand that some sort of soft processor would be the better way to do this. However, its simply for learning.

Code: Select all
`Permutations with repetition (n=3, r=3){a,a,a} {a,a,b} {a,a,c}{a,b,a} {a,b,b} {a,b,c}{a,c,a} {a,c,b} {a,c,c}{b,a,a} {b,a,b} {b,a,c}{b,b,a} {b,b,b} {b,b,c}{b,c,a} {b,c,b} {b,c,c}{c,a,a} {c,a,b} {c,a,c}{c,b,a} {c,b,b} {c,b,c}{c,c,a} {c,c,b} {c,c,c}`
Bobby_

Posts: 3
Joined: Thu Dec 17, 2009 5:16 pm

### Re: Permutations

Think of the problem as a base-3 system. (Decimal is base-10, binary base-2). But you must represent the base-3 number on a base-2 system.

define a wire that is 6 bits wide.
initialize it as 000000 representing aaa.
if the last two bits are 11, then add 1.
if the middle bits are 11, then add 100.
if the top two bits are 11, then you are finished (exclude the last one).
if not finished, decode value and store.
if not finished, repeat from the step where you added 1.
Kreeesh

Posts: 21
Joined: Thu Aug 23, 2007 7:00 am

They need to stay as ascii charters for later use, I will be sending them to RS232 UART.
Thats why I have a 24bit wire.

Or.. do you think it would be better to use a method as you stated then also some sort of decoder to change them back to the correct ascii?
Bobby_

Posts: 3
Joined: Thu Dec 17, 2009 5:16 pm

Bobby_ wrote:They need to stay as ascii charters for later use, I will be sending them to RS232 UART.

In the decoder stage, change them to ascii. Just add the binary equivalent of "aaa" to the number.
Kreeesh

Posts: 21
Joined: Thu Aug 23, 2007 7:00 am

Thanks for your help, I got it working Bobby_

Posts: 3
Joined: Thu Dec 17, 2009 5:16 pm