2
$\begingroup$

***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?

$\endgroup$
0
1
$\begingroup$

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 *)
            MapThread[
                BooleanCountingFunction[{#1}, dim[[1]]] @@ #2 &,
                {w, Transpose @ a}
            ],
            (* make sure each row has only one variable selected *)
            BooleanCountingFunction[{1}, dim[[2]]] @@@ a
        }],
        v,
        All
    ];

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

Example:

SeedRandom[2];
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}}

$\endgroup$
4
  • $\begingroup$ I think you read my mind regarding the handling of the ambiguity. $\endgroup$
    – Hellbound
    Jun 25 at 18:44
  • $\begingroup$ 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. $\endgroup$
    – Hellbound
    Jun 25 at 19:07
  • $\begingroup$ @Hellbound I don't know what the protocol is, but I don't mind you updating your question and removing the accept :) $\endgroup$
    – Carl Woll
    Jun 25 at 20:29
  • $\begingroup$ Alright, I made the edit. Thanks $\endgroup$
    – Hellbound
    Jun 25 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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