All possible ways to split a number

Question

I am trying to find a way to find (if it is possible) how many ways there are to split a number of n digits considering that the "splits" can occur everywhere and the subsets don't have to be the same length. So for example, if I have a 5 digits number "12345" I can split it into 16(?) ways:

1)12345

2)1-2-3-4-5

3)1-2345

4)12-345

5)123-45

6)1-23-45 etc.

So I am looking for all possible strategies to split the number. I am looking for both a formula and an algorithm. I am guessing that it is 2^(n-1) but I am not sure and I'd like to know why, if this is the case

Answer 1

Your problem can be solved using permutation with repetition in general.

Permutations with repetition

Ordered arrangements of the elements of a set S of length n where repetition is allowed are called n-tuples, but have sometimes been referred to as permutations with repetition although they are not permutations in general. They are also called words over the alphabet S in some contexts. If the set S has k elements, the number of n-tuples over S is:

The general formula is $ k^n $ where $k$ is the number of elements of S and $n$ the length of the tuple to form.

There is no restriction on how often an element can appear in an n-tuple, but if restrictions are placed on how often an element can appear, this formula is no longer valid.

In particular your problem to split 5 figures is equivalent to arrange 4 elements ($n=4$) from a set S of 2 elements ($k=2$) i.e.

$\{"-", "Nothing"\}$

in order to get 4 tuples;

$("-/Nothing","-/Nothing","-/Nothing","-/Nothing")$ where slash $/$ means logical operator "or".

Therefore you will get the amount that you have inferred above which:

${2^{4}} = 16$

possible splits.

An algorithm in python 3.5 to solve this problem

import itertools

def getSplits(myciphers):
    comb=[]    
    for split in [p for p in itertools.product([0,1], repeat=4)]:            
        tsplit=[]
        tsplit.append(myciphers[0])
        for c,s in zip(myciphers[1:],split):      
            if s == 1:
                tsplit.append("-")
            tsplit.append(c)

        comb.append("".join(tsplit))
    return comb

# Test Case 1
myciphers="12345"
print(getSplits(myciphers))

# Test Case 2
myciphers="ABCD"
print(getSplits(myciphers))

The output of this program is as follows:

rcolomina@workstation-rig:~$ python boo.py
['12345', '1234-5', '123-45', '123-4-5', '12-345', '12-34-5', '12-3-45', '12-3-4-5', '1-2345', '1-234-5', '1-23-45', '1-23-4-5', '1-2-345', '1-2-34-5', '1-2-3-45', '1-2-3-4-5']
['ABCD', 'ABCD', 'ABC-D', 'ABC-D', 'AB-CD', 'AB-CD', 'AB-C-D', 'AB-C-D', 'A-BCD', 'A-BCD', 'A-BC-D', 'A-BC-D', 'A-B-CD', 'A-B-CD', 'A-B-C-D', 'A-B-C-D']

Answer 2

Look at the cuts as a binary number where each digit i of the number indicates if we cut between digit i and i+1 in the real number.
for example:
12345 would be 0000.
12-345 would be 0100.

Now,for a number of size n our binary number would be of size n-1,how many unique values can a n-1 digits binary number represent?
$$2^{(n-1)}$$.

Answer 3

When you have a sequence of $n$ numbers, you can $n-1$ slots to make cuts. So we need to know all the ways we can choose $0$ cuts out if it, then $1$ cut, $2$ cuts, etc

The total number of ways to choose the cuts is $$\sum_{k=0}^{n-1} { {n-1}\choose{k}} =2^{n-1} $$

To prove this equality, use a subtle trick: Set $2^{n-1} = (1+1)^{n-1}$ and use the Binomial Theorem.