Skip to main content
-1 byte using Tr
Source Link
Misha Lavrov
  • 5.3k
  • 13
  • 27

Wolfram Language (Mathematica), 5353 52 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Length@#&@t[Range@Tr[1^#]&/@#]&

Try it online!Try it online!

Unfortunately, computing the determinant of an n by n matrix this way uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Length@#&t[Range@Tr[1^#]&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 7473 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Length@#&@t[Range@Tr[1^#]&/@#])&

whichreplacing it by 1##&@@Order@@@#~Subsets~{2}&. This computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.


-1 byte thanks to @user202729

Wolfram Language (Mathematica), 53 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Length@#&/@#]&

Try it online!

Unfortunately, computing the determinant of an n by n matrix this way uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Length@#&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 74 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Length@#&/@#])&

which computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.

Wolfram Language (Mathematica), 53 52 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Tr[1^#]&/@#]&

Try it online!

Unfortunately, computing the determinant of an n by n matrix this way uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Tr[1^#]&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 73 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Tr[1^#]&/@#])&

replacing it by 1##&@@Order@@@#~Subsets~{2}&. This computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.


-1 byte thanks to @user202729

space complexity
Source Link
Misha Lavrov
  • 5.3k
  • 13
  • 27

Wolfram Language (Mathematica), 53 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Length@#&/@#]&

Try it online!

Unfortunately, computing the determinant of an n by n matrix this way uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Length@#&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 74 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Length@#&/@#])&

which computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.

Wolfram Language (Mathematica), 53 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Length@#&/@#]&

Try it online!

Unfortunately, uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Length@#&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 74 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Length@#&/@#])&

which computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.

Wolfram Language (Mathematica), 53 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Length@#&/@#]&

Try it online!

Unfortunately, computing the determinant of an n by n matrix this way uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Length@#&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 74 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Length@#&/@#])&

which computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.

replacing Signature
Source Link
Misha Lavrov
  • 5.3k
  • 13
  • 27

Wolfram Language (Mathematica), 53 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Length@#&/@#]&

Try it online!

Unfortunately, uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Length@#&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 74 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Length@#&/@#])&

which computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.

Wolfram Language (Mathematica), 53 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Length@#&/@#]&

Try it online!

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Length@#&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.

Wolfram Language (Mathematica), 53 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Length@#&/@#]&

Try it online!

Unfortunately, uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Length@#&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 74 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Length@#&/@#])&

which computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.

Source Link
Misha Lavrov
  • 5.3k
  • 13
  • 27
Loading