26
\$\begingroup\$

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

\$\endgroup\$
2

21 Answers 21

9
\$\begingroup\$

Brachylog, 8 bytes

ṫ{~cịᵐ}ᵘ

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

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ +1 for codegolf spirit \$\endgroup\$ – Razetime Aug 29 '20 at 14:04
  • 1
    \$\begingroup\$ the output of 101 misses (1,1) which comes from (1, 01) \$\endgroup\$ – ZaMoC Aug 29 '20 at 14:06
  • 1
    \$\begingroup\$ @J42161217 Ah, of course! Fixed for +1 byte. Sadly, this makes it quite fast and removes the codegolf spirit. :-) \$\endgroup\$ – xash Aug 29 '20 at 14:12
  • \$\begingroup\$ Sorry for that..;) +1 \$\endgroup\$ – ZaMoC Aug 29 '20 at 14:14
  • \$\begingroup\$ 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 \$\endgroup\$ – Unrelated String Sep 1 '20 at 13:40
8
\$\begingroup\$

05AB1E, 4 bytes

.œïÙ

Try it online!


Explanation

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

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!

\$\endgroup\$
3
6
\$\begingroup\$

Pyth, 6 bytes

{sMM./

Try it online!

Explanation

{sMM./
    ./  # Partitions of implicit input
 sMM    # Convert to integers (to remove leading 0s)
{       # Deduplicate
\$\endgroup\$
6
\$\begingroup\$

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
 )
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 126 bytes by using combn since you're taking the unique anyway. Not sure about a recursive approach, though. \$\endgroup\$ – Giuseppe Aug 31 '20 at 16:40
  • \$\begingroup\$ Very clever and something that I never would have thought-of! Thanks! \$\endgroup\$ – Dominic van Essen Sep 1 '20 at 9:11
5
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 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) \$\endgroup\$ – Jonathan Allan Aug 29 '20 at 15:40
  • 1
    \$\begingroup\$ @JonathanAllan So it can, I never realised that. Thanks! \$\endgroup\$ – caird coinheringaahing Aug 29 '20 at 15:41
5
\$\begingroup\$

Perl 5 -MList::Util=uniq -F, 108 96 94 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!

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

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.

\$\endgroup\$
3
\$\begingroup\$

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

Remove the leading separator and also leading zeros of any numbers.

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ – ZaMoC Aug 31 '20 at 18:07
  • \$\begingroup\$ 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. \$\endgroup\$ – Lucas Moeskops Aug 31 '20 at 19:41
  • \$\begingroup\$ nice +1. Welcome to code golf! \$\endgroup\$ – ZaMoC Aug 31 '20 at 19:47
2
\$\begingroup\$

Charcoal, 47 bytes

⊞υ⟦S⟧≔⟦⟧θFυ«≔⊟ιη¿ηFLη⊞υ⁺ι⟦I…η⊕κ✂η⊕κ⟧¿¬№θι⊞θι»Iθ

Try it online! Link is to verbose version of code. Explanation:

⊞υ⟦S⟧

Start a breadth first search with the input number.

≔⟦⟧θ

Start with no results.

Fυ«

Loop over the candidates.

≔⊟ιη

Get the current suffix.

¿ηFLη

If the suffix is not empty then loop over all of its proper suffixes...

⊞υ⁺ι⟦I…η⊕κ✂η⊕κ⟧

... 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.

»Iθ

Print all the results. (This uses Charcoal's default output, whereby lists are double-spaced as their entries are printed on separate lines.)

\$\endgroup\$
2
\$\begingroup\$

J, 36 29 bytes

[:~.]<@("./.~+/\)"#.2#:@i.@^#

Try it online!

-7 bytes thank to xash!

Explanation later.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 29 bytes \$\endgroup\$ – xash Aug 29 '20 at 22:55
  • \$\begingroup\$ Great edits. Thanks! \$\endgroup\$ – Jonah Aug 29 '20 at 23:31
2
\$\begingroup\$

Raku, 38 bytes

{unique +<<m:ex/^(.+)+$/>>[0],:as(~*)}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Mathematica 106 bytes

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

Try it online

\$\endgroup\$
1
  • 3
    \$\begingroup\$ 98 bytes This was also my approach. You can save some bytes if you don't use Table \$\endgroup\$ – ZaMoC Aug 30 '20 at 11:43
2
\$\begingroup\$

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:
    S.add(           //   add to the set S:
      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)
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Shouldn't the output be deduplicated? \$\endgroup\$ – Shaggy Sep 3 '20 at 12:18
  • \$\begingroup\$ Deduplicating after the map would get around that for +0bytes: ã cUã)à f_¬¥UîmnÃâ. \$\endgroup\$ – Shaggy Sep 3 '20 at 12:21
  • \$\begingroup\$ 18 bytes \$\endgroup\$ – Shaggy Sep 3 '20 at 12:26
2
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ well golfed! small improvement: 2|^$x -> 2&$x \$\endgroup\$ – ngn Dec 6 '20 at 11:54
  • \$\begingroup\$ i think enlisting the first item should be fine. the examples enclose it with { } which implies it's a list. \$\endgroup\$ – ngn Dec 6 '20 at 11:57
  • 1
    \$\begingroup\$ to avoid the expensive "filter": (~*:)#&'+!2&$ -> &'+1,!1_2&$ \$\endgroup\$ – ngn Dec 6 '20 at 12:02
  • \$\begingroup\$ @ngn: much appreciated! \$\endgroup\$ – coltim Dec 6 '20 at 17:02
1
\$\begingroup\$

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.

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

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!

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

Husk, 14 bytes

ummdf(=d¹Σ)ṖQd

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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]] \$\endgroup\$ – ZaMoC Nov 11 '20 at 9:44
  • \$\begingroup\$ @J42161217 corrected it \$\endgroup\$ – Razetime Nov 11 '20 at 9:49
0
\$\begingroup\$

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
\$\endgroup\$

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.