New answers tagged combinatorics
0
Ruby, 60 bytes
->s{a,*z=s.chars,'';z.product(*a.map{a+z}).map(&:join)-z|[]}
Try it online!
0
Husk, 4 bytes
Total Husk novice, there may be better ways to golf this.
Mπŀ¹
Try it online!
Explanation
ŀ¹ Find the range [1, ..., len(input)]
Mπ Map with cartesian power of input
1
05AB1E, 19 18 bytes
ݦ.s˜œ€Œ€`ÙʒÙāQ}g>
Pretty slow (\$n=3\$ in about 5.5 seconds on TIO), but it works.
Inspired by @isaacg's Pyth answer.
I have the feeling this can definitely be golfed by at least a few bytes, though.
-1 byte thanks to @ExpiredData.
Try it online or verify a few more test cases.
Explanation:
Ý # Push a list in ...
5
Pyth, 13 bytes
lfUI{T{.ysmRh
Try it online!
Let's go through this step by step, starting at the end:
mRh: This autoexpands to mRhdQ. This means "Map the function m with right input hd over the input Q."
Q is an integer (e.g. 3) so it gets automatically cast to a range (e.g. [0, 1, 2]).
The m function is the map function.
d is defined to be the input to ...
2
Raku, 94 bytes
{1+set map ~*,grep {all .unique Z==^$_},.permutations>>[[\,] ^$_][*;*]}o{(^$_ Zxx 1..$_)[*;*]}
Try it online!
Times out for \$n>3\$, mostly since it is running the same filter for all prefixes of all permutations of the largest list (i.e. [1,2,2,3,3,3,...n]). This results in a lot of duplicates that have to filtered out later.
1
Charcoal, 34 bytes
Ｎθ⊞υυＦυＦθＦ∧∨¬κ№ι⊖κ‹№ικ⊕κ⊞υ⁺ι⟦κ⟧ＩＬυ
Try it online! Link is to verbose version of code. Builds up all a(n) lists in memory, so TIO will only go up to n=5. Explanation:
Ｎθ
Input n.
⊞υυ
Start with a sequence with no digits. (Alternatively, I could start with a list containing -1; this would cost 3 bytes here and then save 3 bytes because ...
3
JavaScript (ES6), 91 ... 76 74 bytes
A recursive approach. This is very fast up to \$n=5\$. Computing \$a(6)\$ takes approximately 2 minutes on my laptop.
n=>(g=a=>1+(h=i=>i&&h(i-1)+(a[i]^i&&a[i-1]?g(b=[...a,0],b[i]++):0))(n))`1`
Try it online!
How?
Instead of explicitly building the sequences, we just keep track of ...
1
Perl 5, 150 bytes
sub f{my$n=pop;$n?do{my%e;@f=f($n-1);push@f,map{$f=$_;grep!$e{$_}++,map$f=~s/.{$_}/$&$n/r,$n==1?0:index($f,$n-1)+1||9e9..length$f}@f for 1..$n;@f}:''}
Try it online!
Produces the correct output in about two seconds for up to n=5.
Out of memory for n=6. And would not work anyway for n>9 (two digit numbers).
Thought about using a ...
2
Ruby, 100 bytes
Relatively simple answer similar to the Jelly solution, but it's able to calculate for n=4 without timing out on TIO (albeit taking 30 seconds to do so), which Jelly can't at time of writing.
->n{r=(1..n).flat_map{|j|[j]*j};i=0;r.sum{r.permutation(i+=1).uniq.count{|a|a.uniq==[*1..a.max]}}+1}
Try it online!
4
Jelly, 18 bytes
x`€FŒ!QJƑ$Ƈ¹Ƥ€ẎQL‘
Try it online!
An initial attempt at a Jelly answer. A monadic link taking an integer and returning an integer. Too slow for n>3 on TIO.
Explanation
x`€ | Repeat each of 1..n itself times
F | Flatten
Œ! | Permutations
$Ƈ | Keep those where the following ...
0
R, 112 bytes
function(S,s=sapply)cat(unlist(s(1:nchar(S),function(X)do.call('paste0',expand.grid(s(rep(S,X),strsplit,''))))))
Try it online!
Things that make you go Argh, strings in R.
Expands out to the following
cat( # output the results
unlist( # collapse the list
...
2
Charcoal, 17 bytes
ＦＥθＸＬθ⊕κＥι✂⍘⁺ικθ¹
Try it online! Link is to verbose version of code. Explanation:
ＦＥθＸＬθ⊕κ
Loop over the substring lengths and raise the length to each power in turn.
Ｅι✂⍘⁺ικθ¹
Loop from each power to double its value and perform base conversion using the input string as the alphabet, then slice off the first character.
1
JavaScript (ES7), 90 bytes
Returns a Set.
s=>new Set([...Array(n=(L=-~s.length)**~-L)].map(_=>(g=n=>n?[s[n%L-1]]+g(n/L|0):'')(n--)))
Try it online!
Commented
s => new Set( // build a set from
[...Array( // an array of
n = // n entries, with:
(L = -~s.length) // n = L ** (L - 1)
...
2
PowerShell, 42 bytes
($a=$args)|%{($p=$p|%{$t=$_;$a|%{$t+$_}})}
Try it online.
Expects input via splatting.
12
Scratch 3.0, 65 blocks / 637 632 bytes
Look at y'all, having fun with your fancy shmancy permutation functions/map tools. Well, not I! No, not I! When using Scratch, one has to do things themselves! You won't find any built-ins around these parts! I'm just glad there still ain't any gotos ;)
But more seriously, the image is split into 4 parts because it's ...
1
Python 2, 69 68 bytes
f=lambda s,A={''}:s in A and A or f(s,A|{a+c for a in A for c in s})
Try it online!
Outputs a set; includes the empty string.
Python 2, 71 bytes
f=lambda s,A=[]:s in A and A or f(s,set(s)|{a+c for a in A for c in s})
Try it online!
If empty string is not allowed...
5
Haskell, 34 bytes
f s=init$mapM(\_->s)=<<scanr(:)[]s
Try it online!
Here's how it works, using input s="abc":
scanr(:)[]s
Produces the suffixes of s, ["abc","bc","c",""], by prepending each character in turn to the front and tracking the intermediate results.
mapM(\_->s)
Uses the list monad to map each ...
3
PHP, 176 174 173 171 170 166 bytes
$c=$t=count($u=array_values(array_unique(str_split($argn))));for($s=1;$i<$t**$t;){$i-$c?:[$s++,$c*=$t,$i=0];for($k=$i++,$j=0;$j<$s;$j++,$k/=$t)echo$u[$k%$t];echo',';}
Try it online!
-4 bytes thanks to @Ismael Miguel.
Method: simply count in base N, where N is the number of unique characters in the input string.
2
Burlesque, 5 bytes
JL[cb
Try it online!
J # Duplicate the input...
L[ # ...and get it's length
cb # Get all combinations of the input characters up to the length of the input
7
Jelly, 2 bytes
ṗJ
A monadic Link which accepts a list of characters and returns a list of lists of lists of characters.
Try it online! (footer formats as a grid)
How?
ṗJ - list, S
J - range of length of S
ṗ - Cartesian power (vectorises)
If we must output a flat list of "strings" (lists of characters) we can add Ẏ (tighten) for the cost of a byte.
1
Pyth, 5 bytes
^LQSl
Try it here!
3
J, 16 bytes
a:-.~[:,#\{@#"{<
Try it online!
a:-.~ Remove empty boxes from...
[:, The flatten of...
{@#"{ The Catalog (cross prod) of {@...
#\{@#"{<
< The boxed input...
#"{ Copied this many times...
#\ 1, 2, ... N, where N is the input length. That is, we copy the input once, then twice, ... then N times, taking the Catalog of each of those.
8
05AB1E, 4 3 bytes
-1 byte thanks to a'_'
ā€ã
Try it online!
1
Perl 6, 32 bytes
{flat [\X~] '',|[xx] .comb xx 2}
Try it online!
Anonymous code block that takes a string and returns a list of string including the length zero permutation.
5
05AB1E, 6 bytes
gENIã)
Try it online!
Explanation
gENIã)
E # foreach in...
g # the input
ã # find the cartesian product of...
I # the input...
N # repeat N
) # wrap the final stack to an array
# implicit output of the top element
2
Python 3, 95 bytes
import itertools as i;lambda s:[''.join(p)for l in range(len(s))for p in i.product(s,repeat=l)]
Try it online
1
Brainf*ck, 36 bytes
Cell layout: cells 1 and 2 are input, cell 3 is where the final answer is built, cell 4 is auxiliary
,->,-<[->[->+>+<<]>>[-<<+>>]<<<]>>-.
Or, with words:
,- read a and decrement
> move to cell 2
,- read b and decrement
< ...
1
JavaScript (V8), 13 bytes
a=>b=>a*b-a-b
Try it online!
Same solution as other answers, I almost didn't post it but for once I found a question without a JS answer, so may as well. In fact this is the exact same as Kevin Cruijssen's answer, replacing Java's lambda -> with Javascript's =>. I've included a very basic testing framework in my TIO ...
1
05AB1E, 7 bytes
(ŸãnOQO
Try it online or verify the test cases in the range \$[0,100]\$.
Explanation:
( # Get the negative of the (implicit) input-integer
Ÿ # Push a list in the range [(implicit) input-integer, -input]
ã # Get the cartesian product of this list, creating all possible pairs
n # Square each value in each pair
...
1
MathGolf, 9 bytes
╤■mæ²Σk=Σ
Try it online.
Explanation:
╤ # Take the (implicit) input-integer, and push a list in the range [-input, input]
■ # Take the cartesian product of this, creating a list of all possible pairs
mæ # Map these pairs to, using the following four commands:
² # Take the square of both values in the pair
...
5
GAP
So my previous approach works indeed when we replace the definition of nfa with this:
nfa := Automaton("epsilon", 25, 5,
[[[1,6,7],[2,8,9],[3,10,11],4,5,[6,18],
[7,19],8,9,10,11,[8,22],[9,23],10,11,
0,0,18,19,22,23,0,0,0,0],
[[2,6,13],[3,8,15],[4,10,17],5,0,[8,18],
[13,21],10,15,0,17,[6,22],[15,25],8,17,
10,0,0,...
1
Excel, 12 bytes
=A1*B1-A1-B1
Same approach as other answers.
2
Whitespace, 59 bytes
[S S S N
_Push_0][S N
S _Duplicate_0][T N
T T _Read_STDIN_as_integer][T T T _Retrieve_input][S N
S _Duplicate_input][S N
S _Duplicate_input][T N
T T _Read_STDIN_as_integer][T T T _Retrieve_input][S N
S _Duplicate_input][S T S S T S N
_Copy_0-based_2nd][T S S N
_Multiply_top_two][S N
T _Swap_top_two][T S ...
2
Java 8, 13 bytes
a->b->a*b-a-b
Try it online.
Explanation:
Similar as most other answers, it calculate the product minus the sum:
a->b-> // Method with two integer parameters and integer return-type
a*b // Return the two parameters multiplied by each other,
-a-b // after we've also subtracted both parameters ...
4
APL (Dyalog Unicode), 3 bytes
×-+
Try it online!
Dyadic train where a f b computes (a×b)-(a+b).
Jelly, 3 bytes
×_+
Try it online!
Dyadic link that takes two numbers a and b as left and right arguments. Works the same as the APL version, just with the symbol _ instead of - to represent subtraction.
0
R, 11 7 bytes
a*b-a-b
Where a and b are the 2 numbers.
Thanks to Jo King for pointing out my error.
3
Pyth, 5 bytes
-*FQs
Try it online!
Product minus sum.
t*FtM
Try it online!
a,b -> (a-1)*(b-1)-1
2
C (gcc), 18 bytes
f(a,b){a=~-a*b-a;}
Noodle9's answer except using a= instead of return.
Try it online!
1
Keg, 5 bytes
*¿¿+-
Simply a port of other answers. Uses latest github interpreter.
0
Ruby, 108 bytes
->a{b=[0];m=a.min
(1..1.0/0).map{|n|c=p
a.map{|x|c|=(b!=b-[n-x])}
c&& b<<=n
return n-m if b[-m]&&b[-m]>n-m}}
Try it online!
Explanation
->a{ input list
b=[0]; list of representable integers
m=a.min ...
3
Jelly, 3 bytes
P_S
Try it online!
A monadic link taking a pair of integers. Same method as most other answers (product minus sum).
6
05AB1E, 3 bytes
<P<
Try it online!
< # decrement both inputs
P # product
< # decrement
1
Japt, 4 bytes
×-Ux
Try it here
15
J, 7,6 3 bytes
-1 byte thanks to FrownyFrog !
-3 bytes thanks to Grimmy!
*-+
Try it online!
- subtract
+ the sum of the arguments
* from their product
2
Pyth, 8 7 bytes
t*thQte
Try it online!
Uses the formula (a-1)(b-1) - 1. Takes input as a Python array of 2 integers.
-1 by using implicit appended Q
3
C (clang), 31 22 bytes
f(a,b){return~-a*b-a;}
Try it online!
Saved 9 bytes thanks to ceilingcat!!!
9
Wolfram Language (Mathematica), 8 bytes
1##-+##&
Try it online!
Wolfram Language (Mathematica), 15 bytes
FrobeniusNumber
Try it online!
4
Python 3, 18 bytes
lambda a,b:a*b-a-b
Try it online!
10
Husk, 4 bytes
←¤*←
Try it online!
Explanation
As proved in lots of places, the answer for inputs a and b is ab-a-b = (a-1)(b-1)-1. ¤ is the 'combine' combinator, so ¤*← is a function that applies ← (decrement) to each argument and 'combines' the results by multiplication. Then I decrement the result to get the final output.
4
Perl 6, 43 13 bytes
(*-1)*(*-1)-1
Try it online!
Turns out there's a much shorter way to calculate the answer.
Perl 6, 43 bytes
->\a,\b{max ^(a*b)∖((a X*^b)X+(^a X*b)):}
Try it online!
Top 50 recent answers are included
