0
$\begingroup$

This is an extended version of my previous post, $P=QRS$ decomposition of given list

Based on the answer and comment of @Bill,

Form all permutations of P. Form Q as the first element of each of those, R as the second element and S all the rest of each perm. Then do this with R of length 2. And then of length 3. And ... until you are down to S of length 1. Now start over with Q of length 2, etc, etc, etc.

for length $3$, I have done this via

A3 = Permutations[{a1, a2, a3}]
For[i = 1, i <= Length[A3], i++,
P[i] = Partition[A3[[i]], 1]];
 
For[i = 1, i <= Length[A3], i++,
 Q[i] = P[i][[1]];
 R[i] = P[i][[2]];
 S[i] = P[i][[3]]; ];
Table[Flatten[{Q[i], R[i], S[i]}], {i, 1, Length[A3]}]

It looks okay, but I am having trouble with length 4. With the same instruction I did

A4 = Permutations[{a1, a2, a3, a4}]
Length[A4]
For[i = 1, i <= Length[A4], i++,
 P[i] = Partition[A4[[i]], 1]
 ];

(*2+1+1*)
For[i = 1, i <= Length[A4], i++,
 Q1[i] = Flatten[{P[i][[1]], P[i][[2]]}];
 R1[i] = P[i][[3]];
 S1[i] = P[i][[4]];
  ]
(*1+2+1*)
 For[i = 1, i <= Length[A4], i++,
 Q2[i] = P[i][[1]];
 R2[i] = Flatten[{P[i][[2]], P[i][[3]]}];
 S2[i] = P[i][[4]];
  ]
(*1+1+2*)
 For[i = 1, i <= Length[A4], i++,
 Q3[i] = P[i][[1]];
 R3[i] = P[i][[2]];
 S3[i] = Flatten[{P[i][[3]], P[i][[4]]}];
 ]

But here the size does not agree with what I expected; For length $4$ case there is three choices to divide, $(1,1,2), (1,2,1),(2,1,1)$ and by symmetry, for each of them there are $ 12$ of them so the total is $36$. But here individuals have $24$ and thus $24\times 3=72$.

For example, $\{1,2,3,4\}$ with $(1,1,2)$ decomposition, we have $(1,2,34),(1,3,24),(1,4,23), (2,1,34),(2,3,14),(2,4,13),(3,1,24),(3,2,14),(3,4,12),(4,1,23),(4,2,13),(4,3,12)$ 12 cases [One can think of this first by chossing $2$ elements among $4$ and multiplying the degeneracy $2$]

For $P=QR$ decomposition of an unordered set, the subset is enough for whole possible cases, but in this case, after dividing into $P=QR$ and $R=R'S$, the total size should be increased, and there are some problems for injecting more possible lists into the first partitions.

Before this setup, I just plugging all the possible cases of length $4$ individually, but I realized this is very inefficient and even produces typos(human error) for length $5$ and more than length $5$ cases.

Besides permutations, I tried to formulate similar things with partitions command but I realized the assign function of partition only produces partitions up to its length, not partition into three pieces or more than three. i.e., as a manual says

 Partition[{a, b, c, d, e, f}, 3, 1]

produces sequences of length 3 with offset 1...

Any ideas or explicit examples are welcome!

$\endgroup$

1 Answer 1

1
$\begingroup$

Try this:

A4={a1,a2,a3,a4};
(*ordered*)
p={A4};
i=Permutations[IntegerPartitions[Length[A4],{3}][[1]]];
t=Flatten[Outer[TakeList,p,i,1],1];
Q=Map[#[[1]]&,t];
R=Map[#[[2]]&,t];
S=Map[#[[3]]&,t];

A4={a1,a2,a3,a4};
(*unordered*)
p=Permutations[A4];
i=Permutations[IntegerPartitions[Length[A4],{3}][[1]]];
t=Flatten[Outer[TakeList,p,i,1],1];
Q=Map[#[[1]]&,t];
R=Map[#[[2]]&,t];
S=Map[#[[3]]&,t];

Test this without mercy. Look at the values of p and i and t to make absolutely certain that these are being precisely correctly partitioned into Q and R and S. Perhaps carefully line up corresponding items in Q and R and S and verify that each column of those three rows do partition all of A4 and that every permutation of A4 is correctly included and nothing else is. You really have to convince yourself that this is exactly correct, not just see that a few items seem to be OK and assume that everything must be OK. Then see if you can understand how to generalize this further.

I think I'm beginning to like this. That is dangerous. I need to think more.

$\endgroup$
2
  • $\begingroup$ Hello, using your code, with sorting and dividing multiplicities by hand, I obtain what I want, but wondering about the making size, and the divisions without explicitly. I post this issue at mathematica.stackexchange.com/questions/252816/… $\endgroup$
    – phy_math
    Aug 3, 2021 at 5:55
  • $\begingroup$ I mean, I count the total number by counting multiplicities explicitly. What I want to know in my new posted question is without doing "explicit counting" how one can make consistent counting from the ground. About divisions: For the length 5, case there are 2 possible integerpartitions, so I made [Length[A5],{3}][[1]] and [Length[A5],{3}][[2]] explicitly and do the same thing as length 4; In the new post, I want to know whether there is a systematic way to do this for an arbitrary length of a list; In some sense, we love "generalization" so I make a new post regarding this two issues! $\endgroup$
    – phy_math
    Aug 3, 2021 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.