Is it possible to set rules for calculating permutations of column vectors?

2 次查看（过去 30 天）
badscience
badscience 2019-1-28
评论： badscience 2019-1-29
Forgive me as I am pretty rusty with my MATLAB and general coding.
I am working on some combonitorics and group theory stuff for a math class and essentially need to be able to calculate the number of possible permutations of a column tableau (just a vector in this case) given a set of rules on how that column can be constructed and a given number of elements. This is what I have so far, it just calculates the total number of permutations for each vector and puts those values in a vector of their own.
n=input('Input n value\n');
A=zeros(1,n);
for i=1:n;
v=[1:i]';
P=perms(v1);
A(i)=size(P,1);
end
Here are the rules I want to create for how each permutation is allowed to be created:
Starting from the top element of the column and moving down, entries can decrease in value by exactly 1, or they can increase by any amount. For example, for n=5, a valid permutation could be v=[2, 1, 4, 3, 5]' (notice each subsequent entry either decreases by 1, or increases by some other amount) but an INVALID permutation could be something like v=[5, 3, 2, 1, 4]' (notice 5 decreases to 3, which is a decrease by 2 which is not allowed). I want to be able to create every VALID permutation given an n-value and then count the number of permutations created. Again, I am a little rusty at coding and I hope this makes sense! Thanks in advance!
  8 个评论
显示 6更早的评论
badscience
badscience 2019-1-28
No not at all, but since there are those rules I have to impliment, I am not sure if I will be able to use the perms function. Maybe there is a way MatLab can use the perms function, then go through and count the "Valid" Permutations from the vector of all permutations.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

James Tursa
James Tursa 2019-1-28
编辑：James Tursa 2019-1-28
Use the diff( ) function to calculate all of the permutations, and then count the number of valid ones. E.g.,
P = perms(1:i);
A(i) = sum(all(diff(P,1,2)<=1,2));
This code will, of course, blow up your RAM for large n.
  2 个评论
badscience
badscience 2019-1-28
so in your example, diff(P,1,2) is calculating the difference between adjascent elements of P, and then it is counting the number of times the difference between adjascent elements of P is less than 1?
badscience
badscience 2019-1-29
I just played around with it and got it to work exactly as needed. Thanks for your help, I really appreciate it!

请先登录，再进行评论。

更多回答（1 个）

John D'Errico
John D'Errico 2019-1-29
编辑：John D'Errico 2019-1-29
No, it is not possible to set rules on permutations. At least not unless you write the code to compute those permutations. You have several options.
  • Generate all permutations, throwing out those that are inadmissable under the rules you have been given. This will fail miserably if the number of elements is at all large. What is large? the number of permutations of n elements is factorial(n). Do you really want to deal with trillions of permutations? 15 is not that many elements either.
factorial(15)
ans =
1.3077e+12
  • Do it constructively. Consider a set like [1 2 3 4 5 6]. Each permutation will start with some element. So which permutations can start with 6? By your rules, that can be ONLY the permutation [6 5 4 3 2 1]. (Not difficult to prove.) Next, which permutations can start with 5? Thus 5 can only be followed by 4 or 6 from that set. But then 6 CANNOT be followed by any other number. So any permutation that starts with 5 can only start [5 4...]. What then can follow 4? Again, you will find only one valid sequence. [5 4 3 2 1 6]. You can use similar logic starting from 4. There you will find sequences like [4 3 2 1 5 6] and [4 3 2 1 6 5]. I'd bet you can see the pattern now.
  • At some point, you might think about this as a graph theory problem. Thus for n elements, create the matrix which describes which elements can follow other elements of the set. So G(i,j) = 1 ONLY if element j can follow element i. G(i,j) = 0 otherwise. For the 6 elements [1:6], the matrix decsribing the edges of that graph would be:
G = triu(ones(6),-1) - eye(6)
G =
0 1 1 1 1 1
1 0 1 1 1 1
0 1 0 1 1 1
0 0 1 0 1 1
0 0 0 1 0 1
0 0 0 0 1 0
Now your problem reduces to counting the number of Hamiltonian circuits that exist for that graph.
I imagine there are other ways you could solve this.
  1 个评论
badscience
badscience 2019-1-29
I have some code written with help from James in another answer which calculates all permutations and counts the "valid" ones, but as we are aware, this is not really a good method for large n. It workks really well for small n, but my computer starts chugging around n=11. So I am trying to do this constructiveley. I think starting with this graph theory approach as you suggested may be a good idea.
Thanks for the response!

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Just for fun 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by