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

Question

badscience 2019-1-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/441956-is-it-possible-to-set-rules-for-calculating-permutations-of-column-vectors

评论： 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更早的评论隐藏 6更早的评论

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 2019-1-28

Exactly ... see below.

请先登录，再进行评论。

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

Answer 1

James Tursa 2019-1-28

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/441956-is-it-possible-to-set-rules-for-calculating-permutations-of-column-vectors#answer_358413

编辑：James Tursa 2019-1-28

在 MATLAB Online 中打开

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 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 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!

请先登录，再进行评论。

Answer 2

John D'Errico 2019-1-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/441956-is-it-possible-to-set-rules-for-calculating-permutations-of-column-vectors#answer_358416

编辑：John D'Errico 2019-1-29

在 MATLAB Online 中打开

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 =
   1     1     1     1     1
   0     1     1     1     1
   1     0     1     1     1
   0     1     0     1     1
   0     0     1     0     1
   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 个评论
显示 -1更早的评论隐藏 -1更早的评论

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!

请先登录，再进行评论。