xs = list('01234')
from itertools import combinations
def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        print("smaller :", smaller)
        for n, subset in enumerate(smaller):
            
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller
print(list(partition(list('9457')))       ) 
def gen(arr):
    n = len(arr)
    if n == 1:
        return [arr]
    ans = [arr]
    for k in range(n):
        for c in combinations(range(1, n), r=k):
            a = [arr[0]] + [arr[i] for i in c]
            other = [arr[i] for i in range(1, n) if not i in c]
            for e in gen(other):
                ans.append([''.join(a)] + e)
    return ans

r = set([tuple(x) for x in gen(xs)])

n = 10001
st = str(n)
print(r)
print(len(r))
s = -n
for arr in r:
    _x = [int(''.join(st[int(c)] for c in _s)) for _s in arr]
    print(_x)
    s += sum(_x)
print("s :", s)

def generate_ordered_partitions(arr):
    """
    Generate all ordered partitions where the first element is always 
    in the first subset, and remaining elements are distributed among subsets.
    """
    if not arr:
        return [[]]
    
    if len(arr) == 1:
        return [[arr]]
    
    first_element = arr[0]
    remaining = arr[1:]
    all_partitions = []
    
    # For each possible size of the first subset (1 to len(arr))
    for first_subset_size in range(1, len(arr) + 1):
        # Generate all combinations of (first_subset_size - 1) elements from remaining
        # to include with the first element
        from itertools import combinations
        
        for combo in combinations(remaining, first_subset_size - 1):
            # Create first subset with first element + selected elements
            first_subset = [first_element] + list(combo)
            
            # Get remaining elements (preserving original order)
            remaining_elements = [x for x in remaining if x not in combo]
            
            if not remaining_elements:
                # No more elements to partition
                all_partitions.append([first_subset])
            else:
                # Generate all ordered partitions of remaining elements
                sub_partitions = generate_all_ordered_partitions(remaining_elements)
                for sub_partition in sub_partitions:
                    all_partitions.append([first_subset] + sub_partition)
    
    return all_partitions


def generate_all_ordered_partitions(arr):
    """
    Generate all possible ordered partitions of an array using set partitions
    and maintaining the original order of elements.
    """
    if not arr:
        return [[]]
    
    if len(arr) == 1:
        return [[arr]]
    
    partitions = []
    
    # Use the Bell number approach: for each element after the first,
    # decide which existing subset it joins or if it starts a new subset
    def backtrack(index, current_partition):
        if index == len(arr):
            # Make a deep copy of the current partition
            partitions.append([subset[:] for subset in current_partition])
            return
        
        element = arr[index]
        
        # Try adding element to each existing subset
        for i in range(len(current_partition)):
            current_partition[i].append(element)
            backtrack(index + 1, current_partition)
            current_partition[i].pop()  # backtrack
        
        # Try creating a new subset with this element
        current_partition.append([element])
        backtrack(index + 1, current_partition)
        current_partition.pop()  # backtrack
    
    if arr:
        # Start with first element in its own subset
        backtrack(1, [[arr[0]]])
    
    return partitions


def print_partitions_by_first_subset_size(partitions):
    """
    Print partitions grouped by the size of the first subset.
    """
    from collections import defaultdict
    
    grouped = defaultdict(list)
    for partition in partitions:
        first_subset_size = len(partition[0])
        grouped[first_subset_size].append(partition)
    
    for size in sorted(grouped.keys()):
        print(f"\nPartitions where first element belongs to subset of length {size}:")
        for partition in grouped[size]:
            print(partition)


# Test with the example

arr = list('10001')
print(f"Input array: {arr}")
s = -int(''.join(arr))
partitions = generate_ordered_partitions(arr)
for p in partitions:
    s += sum(int(''.join(x)) for x in p)
print(s)