25
\$\begingroup\$

The cartesian product of two multisets \$A\$ and \$B\$ is the multiset of all ordered pairs consisting of an element of \$A\$ and an element of \$B\$. For example, the cartesian product of \$\{1, 2, 7, 1\}\$ and \$\{4, 6\}\$ is \$\{[1,4],[1,6],[2,4],[2,6],[7,4],[7,6],[1,4],[1,6]\}\$, where the order does not matter.

Your challenge is to, given a nonempty multiset of pairs of positive integers in some order, determine whether it is a cartesian product of two lists - that is, there exist two multisets of positive integers such that their cartesian product is that list. The input may contain multiple identical pairs, may be in any order and may be a cartesian product of two multisets in more than one way.

This is , shortest wins!

Testcases

Truthy

[[1,1]]
[[1,1],[1,2]]
[[1,1],[1,1],[2,1]]
[[1,4],[1,6],[2,4],[7,4],[7,6],[2,6]]
[[4,7],[4,6],[4,5],[4,4]]
[[1,1],[1,1],[1,2],[1,2],[2,1],[2,1],[2,2],[2,2]]
[[1,7],[1,8],[1,9],[1,9],[1,9],[2,7],[2,8],[2,9],[2,9],[2,9],[2,7],[2,8],[2,9],[2,9],[2,9],[3,7],[3,8],[3,9],[3,9],[3,9]]

Falsy

[[1,2],[3,4]]
[[1,2],[2,2],[3,2],[1,3],[2,3]]
[[1,1],[1,1],[1,2],[2,1],[2,2]]
[[1,4],[7,4],[9,6]]
[[6,1],[1,6]]
\$\endgroup\$
12
  • \$\begingroup\$ I don't understand how the third falsy test case is falsy. It seems to be the cartesian product of [1,2] with itself \$\endgroup\$
    – mousetail
    Commented Apr 24 at 14:10
  • 1
    \$\begingroup\$ @emanresuA" but you say that "The input may contain duplicate pairs". Does that mean the orignal sets can contain duplicates, but the cartesian product should never generate a combination of the two items twice? So only if the original set had [1,1,2], it thus can generate it as [1,1], [1,1], [1,2], [2,1], [2,1], [2,2]? \$\endgroup\$ Commented Apr 24 at 21:11
  • 1
    \$\begingroup\$ @willeM_VanOnsem As you can see in the first example, the input may contain duplicate values, and the output should contain the same duplicate pairs. \$\endgroup\$
    – emanresu A
    Commented Apr 24 at 21:25
  • 1
    \$\begingroup\$ @UnrelatedString added \$\endgroup\$
    – emanresu A
    Commented Apr 25 at 1:27
  • 1
    \$\begingroup\$ @emanresuA I share mousetail's and willeM_'s confusion and I believe that it stems from the fact that your post uses the word "input" with two opposite meanings, namely (1) "the two multisets that undergo cartesian product" and (2) "the input to the code, to be assessed as the result of a cartesian product". In particular, when you say «The input may contain duplicate pairs [...] and may be a cartesian product in more than one way» I think you are switching meaning mid-sentence. Please rephrase since, as currently written, the post should treat [[1,1],[1,1],[1,2],[2,1],[2,2]] as truthy. \$\endgroup\$
    – Nicola Sap
    Commented Apr 25 at 8:19

14 Answers 14

13
\$\begingroup\$

Python, 76 bytes

Thanks @att for -1.

lambda L,S=sorted:S(K:=[a+b for a in L for b in L])==S((x*3)[::3]for x in K)

Attempt This Online!

Python, 77 bytes

Thanks @Jonathan Allan for -1.

lambda L:sorted(K:=[a+b for a in L for b in L])==sorted((x*3)[::3]for x in K)

Attempt This Online!

Original

Python, 84 bytes

lambda L:all((C:=L.count)(a)*C(b)==C((a+b)[::3])*C((b+a)[::3])for a in L for b in L)

Attempt This Online!

which implements the main idea more directly.

How?

Checks for every pair of pairs (a,b),(c,d) in the given list L whether the products of counts #(a,b) x #(c,d) and #(a,d) x #(c,b) are equal.

Clearly, this is necessary for L to be a cartesian product.

For sufficiency, observe #(a,b)/#(c,b) = #(a,d)/#(c,d) for any b,d so row a is a multiple of row c. Since this holds for any a,c the matrix of counts has rank <= 1 and can be written as an outer product.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ @JonathanAllan sorry for "working around" your improvement. I was planning to merge it with my new golfs but now it doesn't seem to fit anymore. \$\endgroup\$ Commented Apr 26 at 21:54
  • 1
    \$\begingroup\$ -1 aliasing sorted \$\endgroup\$
    – att
    Commented Apr 27 at 0:58
10
\$\begingroup\$

Jelly, 9 bytes

ŒṬ€SẸƇÆrE

Try it online!

Builds a 2D matrix where each element represents how many times its coordinates appear in the original array, and then passes it to Dennis's rank-1 matrix test. In modern Jelly, Ðf has been superseded by Ƈ.

ŒṬ€SẸƇÆrE    Input: a list of pairs
ŒṬ€          For each pair [a,b], create a matrix with a rows and b cols
             filled with zeros, but with a 1 at the bottom right corner
   S         Sum; pad with zeros as necessary
    ẸƇÆrE    Dennis's rank-1 matrix test:
    ẸƇ       Remove all-zero rows
      Ær     Interpret each row as a polynomial and find its complex
             roots with multiplicity
        E    Test if they are all eqaual

Some rows may be shorter after S (e.g. for input [[1,2], [3,4]]), but it is not a problem because the rightmost element is treated as the highest power, so [0, 0, 0, 1] (x^3) and [0, 1] (x) have roots [0,0,0] and [0] respectively.

\$\endgroup\$
8
\$\begingroup\$

Wolfram Language (Mathematica), 25 bytes

MatrixRank@BinCounts@#<2&

Try it online!

Form a matrix whose entries correspond to the number of times a pair is present in the input. This is a cartesian product of multisets iff all rows/columns of that matrix are linearly dependent, i.e. its rank is at most 1.

Since inputs are nonnegative integers, BinCounts conveniently returns a matrix where (0-indexed) \$i,j\$ is the number of times \$(i,j)\$ appears in the input.

\$\endgroup\$
7
\$\begingroup\$

Brachylog, 6 bytes

\⊇ᵐẋp?

Try it online!

Explanation

\⊇ᵐẋp?
\       Transpose the list of pairs into a pair of lists, each containing the
        elements of one of the multisets (possibly more times than necessary)
 ⊇ᵐ     Take some subset of each list
   ẋ    Cartesian product of those subsets
    p   Take some permutation
     ?  Assert that the result equals the input
\$\endgroup\$
5
\$\begingroup\$

Jelly, 12 bytes

ZṬ€S:g/$Ɗƙ/E

Try it online!

I don't see this getting any shorter, but at least it ties Jonathan Allan's performant variant with a bit more performance.

Z       Ɗƙ/     Group the second column by the first column, and for each group:
    :           Divide
 Ṭ€S            the order-independent multiplicities of the elements
     g/$        by the multiplicities' GCD.
           E    Are the results of every group equal?
\$\endgroup\$
5
\$\begingroup\$

Vyxal 3, 11 bytes

Tᵛ⁺/Ẋᵛ/Ẋ$Ṗ⁾

Outputs empty list for falsey, nonempty list for truthy. Try it Online!

Explanation

Rough port of my Brachylog answer:

Tᵛ⁺/Ẋᵛ/Ẋ$Ṗ⁾
T            Transpose into two lists of elements
 ᵛ⁺          Powerset (all subsets) of each
   /Ẋ        Fold on Cartesian product (all possible pairs of subsets)
     ᵛ/Ẋ     Fold each on Cartesian product (Cart. prod. of each pair)
        $    Swap, pushing original input again
         Ṗ   List of all permutations
          ⁾  Set intersection

That is, some permutation of the input matches one of the Cartesian products.

\$\endgroup\$
5
\$\begingroup\$

Nekomata + -e, 9 bytes

ŤđᵃSᵒÐj↕=

Attempt This Online!

A port of @DLosc's Brachylog answer to Nekomata. Unfortunately, Nekomata doesn't have a built-in for Cartesian product.

ŤđᵃSᵒÐj↕=
Ť           Transpose
 đ          Unpair
  ᵃS        Take a subset of each of the two lists
    ᵒÐ      Generate a 2d array of all possible pairs
      j     Concatenate
       ↕    Permute
        =   Check if equal

Nekomata + -e, 10 bytes

↕JᵐŤŤđ≡¿ᵐ≡

Attempt This Online!

↕JᵐŤŤđ≡¿ᵐ≡  Take [[1,4],[1,6],[2,4],[7,4],[7,6],[2,6]] as an example
↕           Permute
                One possible output: [[1,4],[1,6],[2,4],[2,6],[7,4],[7,6]]
 J          Split into a list of sublists
                One possible output: [[[1,4],[1,6]],[[2,4],[2,6]],[[7,4],[7,6]]]
  ᵐŤŤ       Transpose twice; the original innermost level now becomes the outermost
                [[[1,1],[2,2],[7,7]],[[4,6],[4,6],[4,6]]]
     đ      Unpair
                [[1,1],[2,2],[7,7]], [[4,6],[4,6],[4,6]]
      ≡     Check that all elements in the second list are equal
                [[4,6],[4,6],[4,6]] passes the check
       ¿    And
        ᵐ≡  For each element in the first list, check that all elements are equal
                [[1,1],[2,2],[7,7]] passes the check
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I just now whipped up this monstrosity without Cartesian product--any chance that could port shorter? \$\endgroup\$ Commented Apr 25 at 3:18
  • 1
    \$\begingroup\$ @UnrelatedString Nekomata doesn't have Brachylog's . The shortest I can get is 10 bytes: ↕Jᵐ{Ťđ≡¿}≡ \$\endgroup\$
    – alephalpha
    Commented Apr 25 at 3:38
4
\$\begingroup\$

Vyxal G, 82 bitsv2, 10.25 bytes

fṗƛṖƛøṖƛΠ?⁼}f

don't bother to Try it Online!

Bitstring:

0111011101101100110011101001011010010100001011000101000101000010100100111100011011

So this times out for anything where there's more than two pairs in the input. Basically, anything larger than a 2x2 matrix (iykyk). Possibly because it checks the cartesian product of all possible partitions of all permutations of the powerset of the flattened input. That's like at least \$O((2^n)!)\$ which is already pretty slow.

Most probably high very likely to be golfable somehow.

Explained

fṗƛṖƛøṖƛΠ?⁼}f­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁣⁢​‎‏​⁢⁠⁡‌­
fṗ             # ‎⁡Powerset of the flattened input. Already slow for large inputs. 
  ƛ            # ‎⁢To each set in the powerset:
   Ṗ           # ‎⁣ Get all permutations of that set. Very slow for large inputs with big subsets.
    ƛ          # ‎⁤ To each permutation:
     øṖ        # ‎⁢⁡  Get all the possible ways to split the list. Extremely slow for large inputs
       ƛ       # ‎⁢⁢  To each partition:
        Π      # ‎⁢⁣   Take the cartesian product. For large inputs this means it'll probably never terminate in the lifetime of the universe 
         ?⁼    # ‎⁢⁤   Is that cartesian product equal to the input? 
           }f  # ‎⁣⁡Close all the maps and flatten
# ‎⁣⁢If by some chance all of the above terminates, the G flag gets the maximum of that list. This is basically an any() check
💎

Created with the help of Luminespire.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 11 bytes

FŒPpþ`ẎṢ€iṢ

A monadic Link that accepts a list of pairs and yields 0 (falsey) if not a possible Cartesian product or a positive integer (truthy) if it is.

Try it online! (too slow for any more than four pairs) Or see a reduced test-suite.

How?

FŒPpþ`ẎṢ€iṢ - Link: list of pairs, A
F           - flatten {A} -> all elements
 ŒP         - powerset -> all multisets of all elements
     `      - use as both arguments of:
    þ       -   table of:
   p        -     {muliset 1} Cartesian product {multiset 2}
      Ẏ     - tighten from a table to a list of the Cartiesian products
       Ṣ€   - sort each
          Ṣ - sort {A}
         i  - 1-indexed index of the first occurrence of {sorted A} in
              {sorted products}, or 0 if not found

A slightly faster 12 byte version

ZŒP€pþ/ẎṢ€iṢ

Same I/O as the 11 byter.

Try it online! Or see the test-suite.

How?

ZŒP€pþ/ẎṢ€iṢ - Link: list of pairs, A
Z            - transpose A -> [left elements, right elements]
 ŒP€         - powerset of each -> [potential left m-sets, potential right m-sets]
      /      - reduce by:
     þ       -   table of:
    p        -     {potential left m-set} Cartesian product {potential right m-set} 
       Ẏ     - tighten from a table to a list of the Cartiesian products
        Ṣ€   - sort each
           Ṣ - sort {A}
          i  - 1-indexed index of the first occurrence of {sorted A} in
               {sorted products}, or 0 if not found
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 14 (or 13) bytes

ø€æ`âε`â{I{Q}à

Try it online or verify all test cases.

Should have been 13 bytes (but a lot slower) if it weren't for a bug in the (flattened) maximum builtins à/Z/M for a list of lists containing empty lists, by changing {I{Q to œ€Q: (don't) try it online.

Explanation:

ø             # Zip/transpose; swapping rows/columns of the (implicit) input
 €            # Map over both inner lists:
  æ           #  Get its powerset
   `          # Pop and push both powersets separately to the stack
    â         # Take the cartesian product to create all pairs of lists
     ε        # Map over each pair of lists:
      `       #  Pop and push both lists separately to the stack
       â      #  Take the cartesian product to create all pairs of values
        {     #  Sort the list of pairs
         I    #  Push the input
          {   #  Sort its pairs as well
           Q  #  Check if both sorted lists of pairs are the same
     }à       # After the map: check if any is truthy by leaving its maximum
              # (after it is output implicitly as result)
        œ     #  Get all permutations of this list of pairs
         €    #  Inner map over each pair:
          Q   #   Check if this list of pairs is equal to the (implicit) input-list
     }à       # After the map: check if any inner value is truthy (flattened max)
\$\endgroup\$
4
\$\begingroup\$

JavaScript (Node.js), 84 bytes

x=>!x.some(e=>(g=c=>x.map(t=>s+=t.every((u,i)=>i-c|u==e[i]),s=0)|s)``*g(1)-g()*g(2))

Try it online!

-6 from att
-1 from Arnauld

\$\endgroup\$
2
  • \$\begingroup\$ 87 bytes \$\endgroup\$
    – att
    Commented Apr 24 at 14:25
  • \$\begingroup\$ 86 bytes (from att's version) or 85 bytes with true/false inverted. \$\endgroup\$
    – Arnauld
    Commented Apr 24 at 17:42
3
\$\begingroup\$

Charcoal, 27 bytes

⬤θ⬤θ⁼×№θι№θλΠE²№θE²§⎇⁼νπιλπ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a Cartesian product, nothing if not. Explanation: Port of @Albert.Lang's Python answer.

 θ                          Input list
⬤                           All values satisfy
   θ                        Input list
  ⬤                         All values satisfy
      №                     Count of
        ι                   Outer value
       θ                    In input list
     ×                      Multiplied by
         №                  Count of
           λ                Inner value
          θ                 In input list
    ⁼                       Equals
              ²             Literal integer `2`
             E              Map over implicit range
               №            Count of
                  ²         Literal integer `2`
                 E          Map over implicit range
                      ν     Inner index
                     ⁼      Equals
                       π    Innermost index
                    ⎇       If true then
                        ι   Outermost value
                         λ  Else outer value
                   §        Indexed by
                          π Innermost index
                θ           In input list
            Π               Take the product
                            Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Python 3, 174 bytes

def f(a):x,y=zip(*a);return any(sorted(a)==sorted([[k]+[l]for k in i for l in j])for i in g(*x)for j in g(*y))
g=lambda x=0,*a:x and[i+j for i in[[x],[]]for j in g(*a)]or[[]]

Try it online!

f is the main function and g returns all subsets for a given input.

\$\endgroup\$
1
\$\begingroup\$

Uiua, 45 characters

F←⍣(×/×♭⊞(⊞=.÷).:/×♭⊞=.⊕(∩⊏,⟜⍏⊕(⊃⊢⧻)⊛.)⊛°⊟⍉)0

Try it here!

Using the algorithm:

If, when the pairs are grouped according to first digit, the groups contain second digit multisets whose item counts are multiples of each other, the set is a cartesian product.

Which is apparently less golfy than some of the other algorithms that have been used.

\$\endgroup\$

Your Answer

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

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