Csdrhrt

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

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']

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.

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)}$$.