Is it possible to set rules for calculating permutations of column vectors?
4 次查看(过去 30 天)
显示 更早的评论
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 个评论
采纳的回答
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.
更多回答(1 个)
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.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!