# Split a number in every possible way

You task here is very simple:
Given a positive integer n without leading zeroes as input, split it in all possible ways

## Examples

Input->Output

111  -> {{111}, {1, 11}, {11, 1}, {1, 1, 1}}

123  -> {{123}, {12, 3}, {1, 23}, {1, 2, 3}}

8451 -> {{8451}, {845, 1}, {8, 451}, {84, 51}, {84, 5, 1}, {8, 45, 1}, {8, 4, 51}, {8, 4, 5, 1}}

10002-> {{10002},{1,2},{10,2},{100,2},{1000,2},{1,0,2},{10,0,2},{100,0,2},{1,0,0,2},{10,0,0,2},{1,0,0,0,2}}

42690-> {{42690}, {4269, 0}, {4, 2690}, {426, 90}, {42, 690}, {426, 9, 0}, {4, 269, 0}, {4, 2, 690}, {42, 69, 0},  {42, 6, 90}, {4, 26, 90}, {42, 6, 9, 0}, {4, 26, 9, 0}, {4, 2, 69, 0}, {4, 2, 6, 90}, {4, 2, 6, 9,  0}}


## Rules

Leading zeroes, if they occur, should be removed.
Duplicate partitions in your final list should also be removed.
The order in which the partitions appear in the final list is irrelevant.

This is code-golf. Shortest answer in bytes, wins!

Sandbox

• I think would be good question is to compute the power set Commented Aug 30, 2020 at 3:29
• @marshalcraft That already exists Commented Aug 30, 2020 at 13:53

# Brachylog, 8 bytes

ṫ{~cịᵐ}ᵘ


Convert to string ṫ and get all unique {…}ᵘ reverse concatenations ~c mapped to integers ịᵐ (to remove leading zeros).

Try it online!

• +1 for codegolf spirit Commented Aug 29, 2020 at 14:04
• the output of 101 misses (1,1) which comes from (1, 01) Commented Aug 29, 2020 at 14:06
• @J42161217 Ah, of course! Fixed for +1 byte. Sadly, this makes it quite fast and removes the codegolf spirit. :-)
– xash
Commented Aug 29, 2020 at 14:12
• Sorry for that..;) +1 Commented Aug 29, 2020 at 14:14
• I was going to say "no need to make it faster, it works on my machine if you give it an hour", but it might take that long to even get through the first test case... and I thought I was clever trying ℕᵐc as a generator with reversed arguments, but it runs out of global stack instantly! And ~cℕᵐ, which handles the three digit cases fine on TIO, infinitely repeats the partitions locally... that's probably my issue with {~cȧᵐ}ᵘ, come to think of it, just opaquely Commented Sep 1, 2020 at 13:40

# 05AB1E, 4 bytes

.œïÙ


Try it online!

### Explanation

.œ      - Partitions of implicit input
ï     - Converted to integers (will remove leading 0s)
Ù    - Uniquified
- Output implicitly


# Python 3, 87 bytes

f=lambda s:{(int(s),)}|{a+b for i in range(1,len(s))for a in f(s[:i])for b in f(s[i:])}


Try it online!

• This one requires the input to be a string, which I'm not sure is valid? :-) Commented Aug 31, 2020 at 17:16
• @LucasMoeskops, codegolf.meta.stackexchange.com/a/18097/91267 Commented Aug 31, 2020 at 18:03
• Thanks for the info and sorry for the accusation! Commented Aug 31, 2020 at 19:32

# Pyth, 6 bytes

{sMM./


Try it online!

## Explanation

{sMM./
./  # Partitions of implicit input
sMM    # Convert to integers (to remove leading 0s)
{       # Deduplicate


# R, 136 126 bytes

Edit: -10 bytes thanks to Giuseppe

function(s,n=nchar(s))unique(lapply(apply(!combn(rep(1:0,n),n-1),2,which),function(i)as.double(substring(s,c(1,i+1),c(i,n)))))


Try it online!

Hmm... I suspect that this mayn't be the shortest way... but so far my attempts at recursive solutions have been even longer...

Commented code:

split_number=
function(s,n=nchar(s))                # s=input number (converted to string), n=digits
unique(                              # output unique values from...
lapply(                             # ...looping over all...
apply(                             # ...combinations of breakpoints by selecting all...
!combn(rep(1:0,n),n-1),           # ...combinations of TRUE,FALSE at each position...
1,which),                        # ...and finding indices,
function(i)                        # ...then, for each combination of breakpoints...
as.double(                        # ...get numeric value of...
substring(s,c(1,i+1),c(i,n))     # ...the substrings of the input number
)

• 126 bytes by using combn since you're taking the unique anyway. Not sure about a recursive approach, though. Commented Aug 31, 2020 at 16:40
• Very clever and something that I never would have thought-of! Thanks! Commented Sep 1, 2020 at 9:11

# Jelly, 5 4 bytes

ŒṖḌQ


Try it online!

-1 byte thanks to Jonathan Allan

## How it works

ŒṖḌQ - Main link. Takes an integer as argument (e.g. n = 42690)
ŒṖ   - Get all partitions. Automatically cast to digits  [[4, 2, 6, 9, 0], [4, 2, 6, [9, 0]], [4, 2, [6, 9], 0], [4, 2, [6, 9, 0]], [4, [2, 6], 9, 0], [4, [2, 6], [9, 0]], [4, [2, 6, 9], 0], [4, [2, 6, 9, 0]], [[4, 2], 6, 9, 0], [[4, 2], 6, [9, 0]], [[4, 2], [6, 9], 0], [[4, 2], [6, 9, 0]], [[4, 2, 6], 9, 0], [[4, 2, 6], [9, 0]], [[4, 2, 6, 9], 0], [4, 2, 6, 9, 0]]
Ḍ  - Convert each list back to digits                  [[4, 2, 6, 9, 0], [4, 2, 6, 90], [4, 2, 69, 0], [4, 2, 690], [4, 26, 9, 0], [4, 26, 90], [4, 269, 0], [4, 2690], [42, 6, 9, 0], [42, 6, 90], [42, 69, 0], [42, 690], [426, 9, 0], [426, 90], [4269, 0], 42690]
Q - Remove duplicates                                 [[4, 2, 6, 9, 0], [4, 2, 6, 90], [4, 2, 69, 0], [4, 2, 690], [4, 26, 9, 0], [4, 26, 90], [4, 269, 0], [4, 2690], [42, 6, 9, 0], [42, 6, 90], [42, 69, 0], [42, 690], [426, 9, 0], [426, 90], [4269, 0], 42690]
- Implicit output

• The leadingD is redundant since partitions(array) performs an array = iterable(array, make_digits = True) upfront. (the wiki text "Partition of z (z must be a list)." is somewhat misleading) Commented Aug 29, 2020 at 15:40
• @JonathanAllan So it can, I never realised that. Thanks! Commented Aug 29, 2020 at 15:41

# Perl 5-MList::Util=uniq -F, 1089694 90 bytes

say uniq map{@b=(sprintf'%b',$_)=~/./g;$_="@F
";s/ /','x pop@b/ge;s/\d+/$&*1/reg}1..2**$#F


Try it online!

• Building on your solution, I was able to cut 22 bytes in tio.run/##K0gtyjH9/… Commented Sep 4, 2020 at 14:20

# Scala, 139...104 94 bytes

def f(? :String):Set[_]=Set(?)++(for{< <-1 to?.size-1
x<-f(?take<)
y<-f(?drop<)}yield x+","+y)


Try it online!

A recursive method. The input has to be a string.

# Retina 0.8.2, 59 bytes

\G\d
$&$'¶$,$&
+%)^.+¶

m^,|\b0+\B

O
m^(.+)(¶\1)+1


Try it online! Link includes test cases. Explanation:

\G\d
$&$'¶$,$&


Create copies of the line with all possible proper prefixes of the first number on the line.

^.+¶



If there were any such prefixes, delete the original line.

+%)


Repeat until no more prefixes can be generated.

m^,|\b0+\B



O
m^(.+)(¶\1)+1


Sort and deduplicate the results.

For the Retina 1 port, the biggest saving comes from deduplication, which is basically a built-in in Retina 1. The newlines aren't included in the deduplication, so another stage is needed to filter out blank lines, but it's still a saving of 14 bytes. Another 3 bytes can be saved by using $" which is a shorthand for $'¶$. I also tried using an L stage to avoid leaving the original line but then a conditional is required to end the loop which means that the byte count ends up unchanged. # Python 3, 81 bytes f=lambda g:{(int(g),)}|{b+(int(g[i:]),)for i in range(1,len(g))for b in f(g[:i])}  Try it online! • You can take input as a string as long as you get the correct results without leading zeroes. Please provide a TIO link so that anyone can test your code. Commented Aug 31, 2020 at 18:07 • Okay, thanks! I made the TIO, and saw that my answer was incorrect so I made some adjustments, so it is now 81 bytes instead of 79, but gives the correct answer to all examples. Commented Aug 31, 2020 at 19:41 • nice +1. Welcome to code golf! Commented Aug 31, 2020 at 19:47 # Charcoal, 47 bytes ⊞υ⟦Ｓ⟧≔⟦⟧θＦυ«≔⊟ιη¿ηＦＬη⊞υ⁺ι⟦Ｉ…η⊕κ✂η⊕κ⟧¿¬№θι⊞θι»Ｉθ  Try it online! Link is to verbose version of code. Explanation: ⊞υ⟦Ｓ⟧  Start a breadth first search with the input number. ≔⟦⟧θ  Start with no results. Ｆυ«  Loop over the candidates. ≔⊟ιη  Get the current suffix. ¿ηＦＬη  If the suffix is not empty then loop over all of its proper suffixes... ⊞υ⁺ι⟦Ｉ…η⊕κ✂η⊕κ⟧  ... push the next candidate, which is the prefixes so far, the current prefix cast to integer, and the current suffix. ¿¬№θι⊞θι  But if it is empty and the resulting split is unique then push it to the results. »Ｉθ  Print all the results. (This uses Charcoal's default output, whereby lists are double-spaced as their entries are printed on separate lines.) # J, 36 29 bytes [:~.]<@("./.~+/\)"#.2#:@i.@^#  Try it online! -7 bytes thank to xash! Explanation later. • 29 bytes – xash Commented Aug 29, 2020 at 22:55 • Great edits. Thanks! Commented Aug 29, 2020 at 23:31 # Raku, 38 bytes {unique +<<m:ex/^(.+)+$/>>[0],:as(~*)}


Try it online!

# Mathematica 106 bytes

Union@Table[FromDigits/@#~TakeList~i,{i,Join@@Permutations/@IntegerPartitions@Length@#}]&@IntegerDigits@#&


Try it online

• 98 bytes This was also my approach. You can save some bytes if you don't use Table Commented Aug 30, 2020 at 11:43

# JavaScript (ES6), 88 bytes

Expects a string. Returns a Set of comma-separated strings.

f=([c,...a],o='',S=new Set)=>c?f(a,o+c,o?f(a,o+[,c],S):S):S.add(o.replace(/\d+/g,n=>+n))


Try it online!

### How?

It's important to note that Set.prototype.add() returns the set itself. And because the recursion always ends with S.add(...), each call to f returns S.

### Commented

NB: alternate slash symbols used in the regular expression to prevent the syntax highlighting from being broken

f = (                // f is a recursive function taking:
[c,                //   c   = next digit character
...a],         //   a[] = array of remaining digits
o = '',            //   o   = output string
S = new Set        //   S   = set of solutions
) =>                 //
c ?                // if c is defined:
f(               //   do a recursive call:
a,             //     pass a[]
o + c,         //     append c to o
o ?            //     if o is non-empty:
f(           //       do another recursive call
a,         //         pass a[]
o + [, c], //         append a comma followed by c to o
S          //         pass S
)            //       end of recursive call (returns S)
:              //     else:
S            //       just pass S as the 3rd argument
)                //   end of recursive call (returns S)
:                  // else:
o.replace(     //     the string o with ...
∕\d+∕g,      //       ... all numeric strings
n => +n      //       coerced to integers to remove leading zeros
//       (and coerced back to strings)
)              //     end of replace()
)                //   end of add() (returns S)


# Japt, 18 bytes

ã
cU à f_¬¥NÃ®mnÃâ


Try it

• Saved 1 thanks to @Shaggy !
    ã                  - substrings of input
cUã)             - concatenated to substrings of input(repeated)
à            - combinations
f_¬¥N      - take combinatons if == input when joined
®mn  - deduplicates ( @Shaggy ® )
Ãâ    - implicitly returns unique elements

• Shouldn't the output be deduplicated? Commented Sep 3, 2020 at 12:18
• Deduplicating after the map would get around that for +0bytes: ã cUã)à f_¬¥UÃ®mnÃâ. Commented Sep 3, 2020 at 12:21
• 18 bytes Commented Sep 3, 2020 at 12:26

# K (ngn/k), 32 25 bytes

-4 bytes from not de-listing first result

-3 bytes from @ngn's improvements

{?.''(&'+1,!1_2&$x)_\:$x}


Try it online!

• &'+1,!1_2&$x returns the subset of the (power set of indices of the input) that begin with 0. The original power set index generation code was taken from @JohnE's answer on a different question, and includes improvements from @ngn's comments on this answer. • (...)_\:$x cuts the stringified-input on each of the specified indices
• ?.'' converts each slice to integers, taking the distinct elements
• well golfed! small improvement: 2|^$x -> 2&$x
– ngn
Commented Dec 6, 2020 at 11:54
• i think enlisting the first item should be fine. the examples enclose it with { } which implies it's a list.
– ngn
Commented Dec 6, 2020 at 11:57
• to avoid the expensive "filter": (~*:)#&'+!2&$ -> &'+1,!1_2&$
– ngn
Commented Dec 6, 2020 at 12:02
• @ngn: much appreciated! Commented Dec 6, 2020 at 17:02

# Ruby, 127 bytes

->(n,f=->(s){s.size.times.map{|i|([f.(s[0...i])].flatten(i>1?1:0).map{|j|[j.flatten<<s[i..-1]]})}.flatten(2)}){f.(n.to_i.to_s)}


Try it online!

Explanation

1. first lambda takes a number and a function as parameters
2. second parameter defaults to the lambda that computes the partition
3. the second lambda is called with the number stripped of leading zeroes
4. computation starts with a map for each split point in the number
5. recursively call lambda for the substring before the split point
6. append the substring after the split point to each resulting partition array

judicious array creation [] and applications of flatten in the code ensure exactly one level of array nesting in the result.

# Perl 5, 87 bytes

sub f{$_=pop;/(.)(.+)/?do{my$s=$1;map s/@_\d+/0+$&/ger,map{("$s$_",$s.$_)}f(1,$2)}:$_}


Try it online!

Ungolfed:

sub f {
$_ = pop; # set$_ to input (last arg)
if( /(.)(.+)/ ) {             # if input two or more digits, split
# into start digit and rest
my $s =$1;                 # store start digit
return
map s/@_\d+/0+$&/ger, # no @_ => 1st recursive level => trim leading 0s # 0+$& means int(digits matched)
map { ("$s$_", "$s$_") } # return "start+space+rest" and "start+rest"...
f(1, $2) # ...for every result of rest # (1 marks recursive level below first) } else { return$_                   # if just one digit, return that
}
}


# Perl 5 -MList::Util, 68 bytes

...which is further golfed from the answer from @xcali

say uniq map"@F
"=~s| |$_/=2;','x($_%2)|reg=~s|\d+|\$&*1|reg,1..2**@F


Try it online!

# Husk, 14 bytes

ummdf(=d¹Σ)ṖQd


Try it online!

• If you input 101, this returns [[1,0,1],[10,1],[0,10,1],[1,1],[0,1,1],[101],[0,101]] while it should return [[101],[1,1],[10,1],[1,0,1]] Commented Nov 11, 2020 at 9:44
• @J42161217 corrected it Commented Nov 11, 2020 at 9:49

# Pip-p, 44 bytes

YaUQ({(a|>0)RMx}M({y=aRMs?a^sx}M(PMaJs)))RMx


Probably my craziest Pip answer. There's definitely a shorter method, but I decided to roll with this.

-p pretty prints the final list for easier verification. Takes a very long time with 5 digit numbers.

Try it online!

## Explanation

YaUQ({(a|>0)RMx}M({y=aRMs?a^sx}M(PMaJs)))RMx a → first command line argument
Ya                                           Yank a into variable y
PMaJs       join each element of a with a space, get permutations
{y=aRMs?a^sx}M             filter out the permutations that are not in order
{(a|>0)RMx}M                            Strip leading zeros and empty strings in each split
RMx remove empty strings from the whole result
UQ                                         print the unique splits
`