help:how to generate different combinations of a sequence

[austinpowers]

suppose i have an intial sequence [1 2 3]

i want to genereate all different possible combinations of sequence like

1 2 3
1 3 2
2 3 1
2 1 3
3 1 2
3 2 1

i want to generate this inside an inner loop,and everytime i come inside this innerloop i want to take a different combination

suppose when i first come inside the inner loop and select a sequence , next time when i come into inner loop again i dont want to select already selected sequence ,so everytime i want to select a different sequence.

can anyone help me with this.

 

[GregLocock]

I'd use some sort of sorted encoding, eg raise each member to the power of the prime of that position.

EG

1 2 3

=5^1 + 3^2 +2^3

=5+9+8
=22

each code generated is unique.

Then you can sort and check whether your next suggestion has already ben generated.





Cheers

Greg Locock

Please see FAQ731-376 for tips on how to make the best use of Eng-Tips.

 

[SomptingGuy]

I would pre-generate the entire list of possibilities and a random index vector. Then in my loop I would step through the index vector to indirectly address the entire list one at a time. Something like:


% Example set of values to permute
x=[5 6 7];

% Create all permutations
n=length(x);
idx=dec2base(0:n^n-1,n)+1-'0';
allperms=x(idx);

% Create a random indexing vector
m=size(idx,1);
index=randperm(m);

% Loop through indexing vector
for i=1:m
val=allperms(index(i),;
disp(val)
end

 

[SomptingGuy]

Oops, didn't quite read the question properly - my allperms matrix is too big. But the princple is still the same - just need to compute allperms differently. (the code is somewhat simpler)



% Example set of values to permute
x=[5 6 7];

% Create all permutations
allperms=perms(x);

% Create a random indexing vector
m=size(allperms,1);
index=randperm(m);

% Loop through indexing vector
for i=1:m
val=allperms(index(i),;
disp(val)
end

 

[austinpowers]

that statement allperms=perms(x) is not working, when i am trying to execute that program, the execution stops right there and system takes a lot of time and returns nothing, i think its getting hanged there

 

[SomptingGuy]

How many elements do you have? perms() only works for a few - check its help page.

 

[austinpowers]

i may get upto 20 to 40 elements . if not perms is there any other way of doing this , getting all possible combinations a sequence of elements


can anyone help me with this

 

[SomptingGuy]

Do you really want to store between 2e18 (20!) and 8e47 (40!) permutations and then randomly select? I think Greg's method or a variation on it is the only viable method for a problem like this.

It doesn't scale too well though. Each selection will require a longer search back through those already used.

 

[austinpowers]

yeah , i want to generate all possible combinations n! set , and every time i want to assign a new and different sequence from that set,

is there any alternative way of doing this other than perms approach.

can anyone help me with this.

 

[SomptingGuy]

Wow, if you have a computer that can generate and store n! perms (where n=40) then I'd like to borrow it.

 

[austinpowers]

i dont know about matlab , but in perl its simple and can generate that n!. if perl can generate that using some system configuration then matlab should also be able to generate that for the same system configuration . so i dont think its a system problem

 

[MikeyP]

To store that many combinations would require more (by several orders of magnitude) storage space than exists in all the computers in the world. I think you should go with Greg's approach.

1. Start loop
2. Generate a random permutation
3. Check to see if you have used that permutation before (very unlikey for permutations of 40 elements)
4. do whatever you have to do with that sequence
5. store the sequence in (or a uniquely coded version of it) in the checklist
6. end loop

M

--
Dr Michael F Platten