# Weighted partitions of a matrix

***Made an important edit to make the "partition" part of the question more clear

Let $$m,n$$ be positive integers. Denote $$\left[ m\right] \equiv \{ 1,\ldots ,m\}$$.

Let $$\mathbf{w} \equiv \left(w_1, \ldots, w_n \right)$$ be a weight, so that $$w_j \in \left[ m \right] \cup \{ 0 \}$$ and $$w_1 + \dots + w_n = m$$.

Let $$\mathbf{A}$$ be a matrix of dimensions $$m \times n$$.

For a given matrix $$\mathbf{A}$$ and weight $$\mathbf{w}$$ I want to list all possible lists, where each list consists of exactly one element from each and every row of $$\mathbf{A}$$, so $$m$$ elements in total, such that the first $$w_1$$ elements are from the first column of $$\mathbf{A}$$, the next $$w_2$$ elements are from the second column of $$\mathbf{A}$$, ... the next $$w_j$$ elements are from the $$j$$-th column of $$\mathbf{A}$$, ... and the last $$w_n$$ elements are from the $$n$$-th column of $$\mathbf{A}$$. (Notice that some $$w_j$$'s may be $$0$$, also the $$w_j$$'s are not necessarily pairwise distinct)

What is a nice way to do this?

Update

For the modified question, you could use SatisfiabilityInstances:

partitionedLists[w_, A_?MatrixQ] := Module[{dim=Dimensions[A], a, x, v, f, i},
(* array of variables *)
a = Array[x, dim];

(* variable list, transposed so that column 1 variables come before column 2, etc *)
v = Flatten @ Transpose @ a;

i = SatisfiabilityInstances[
And @@ Flatten[{
(* pick the right number for each column *)
BooleanCountingFunction[{#1}, dim[]] @@ #2 &,
{w, Transpose @ a}
],
(* make sure each row has only one variable selected *)
BooleanCountingFunction[{1}, dim[]] @@@ a
}],
v,
All
];

f = Flatten  @ Transpose @ A;
Pick[f, #]& /@ i
]


Example:

SeedRandom;
w = {2, 1, 2}
A = RandomInteger[10, {5, 3}]


{2, 1, 2}

{{8, 4, 5}, {4, 7, 4}, {0, 1, 0}, {4, 3, 7}, {3, 0, 2}}

Partitioned lists:

partitionedLists[w, A]


{{8, 4, 1, 7, 2}, {8, 4, 3, 0, 2}, {8, 4, 0, 0, 7}, {8, 0, 7, 7, 2}, {8, 0, 3, 4, 2}, {8, 0, 0, 4, 7}, {8, 4, 7, 0, 2}, {8, 4, 1, 4, 2}, {8, 4, 0, 4, 0}, {8, 3, 7, 0, 7}, {8, 3, 1, 4, 7}, {8, 3, 3, 4, 0}, {4, 0, 4, 7, 2}, {4, 0, 3, 5, 2}, {4, 0, 0, 5, 7}, {4, 4, 4, 0, 2}, {4, 4, 1, 5, 2}, {4, 4, 0, 5, 0}, {4, 3, 4, 0, 7}, {4, 3, 1, 5, 7}, {4, 3, 3, 5, 0}, {0, 4, 4, 4, 2}, {0, 4, 7, 5, 2}, {0, 4, 0, 5, 4}, {0, 3, 4, 4, 7}, {0, 3, 7, 5, 7}, {0, 3, 3, 5, 4}, {4, 3, 4, 4, 0}, {4, 3, 7, 5, 0}, {4, 3, 1, 5, 4}}

• I think you read my mind regarding the handling of the ambiguity. Jun 25, 2021 at 18:44
• I have already accepted your answer, but unfortunately I made a mistake when asking my question. I should have mentioned that I wanted to list all possible aforementioned lists, but where exactly one element is taken from each and every row. Jun 25, 2021 at 19:07
• @Hellbound I don't know what the protocol is, but I don't mind you updating your question and removing the accept :) Jun 25, 2021 at 20:29
• Alright, I made the edit. Thanks Jun 25, 2021 at 21:03