How to resolve the algorithm Ordered partitions step by step in the Python programming language

Published on 12 May 2024 09:40 PM
#Python

How to resolve the algorithm Ordered partitions step by step in the Python programming language

Table of Contents

Problem Statement

In this task we want to find the ordered partitions into fixed-size blocks. This task is related to Combinations in that it has to do with discrete mathematics and moreover a helper function to compute combinations is (probably) needed to solve this task.

p a r t i t i o n s (

a r g

1

,

a r g

2

, . . . ,

a r g

n

)

{\displaystyle partitions({\mathit {arg}}{1},{\mathit {arg}}{2},...,{\mathit {arg}}_{n})}

should generate all distributions of the elements in

{ 1 , . . . ,

Σ

i

1

n

a r g

i

}

{\displaystyle {1,...,\Sigma {i=1}^{n}{\mathit {arg}}{i}}}

into

n

{\displaystyle n}

blocks of respective size

a r g

1

,

a r g

2

, . . . ,

a r g

n

{\displaystyle {\mathit {arg}}{1},{\mathit {arg}}{2},...,{\mathit {arg}}_{n}}

. Example 1:

p a r t i t i o n s ( 2 , 0 , 2 )

{\displaystyle partitions(2,0,2)}

would create: Example 2:

p a r t i t i o n s ( 1 , 1 , 1 )

{\displaystyle partitions(1,1,1)}

would create: Note that the number of elements in the list is (see the definition of the binomial coefficient if you are not familiar with this notation) and the number of elements remains the same regardless of how the argument is permuted (i.e. the multinomial coefficient). Also,

p a r t i t i o n s ( 1 , 1 , 1 )

{\displaystyle partitions(1,1,1)}

creates the permutations of

{ 1 , 2 , 3 }

{\displaystyle {1,2,3}}

and thus there would be

3 !

6

{\displaystyle 3!=6}

elements in the list. Note: Do not use functions that are not in the standard library of the programming language you use. Your file should be written so that it can be executed on the command line and by default outputs the result of

p a r t i t i o n s ( 2 , 0 , 2 )

{\displaystyle partitions(2,0,2)}

. If the programming language does not support polyvariadic functions pass a list as an argument. Notation Here are some explanatory remarks on the notation used in the task description:

{ 1 , … , n }

{\displaystyle {1,\ldots ,n}}

denotes the set of consecutive numbers from

1

{\displaystyle 1}

to

n

{\displaystyle n}

, e.g.

{ 1 , 2 , 3 }

{\displaystyle {1,2,3}}

if

n

3

{\displaystyle n=3}

.

Σ

{\displaystyle \Sigma }

is the mathematical notation for summation, e.g.

Σ

i

1

3

i

6

{\displaystyle \Sigma _{i=1}^{3}i=6}

(see also [1]).

a r g

1

,

a r g

2

, . . . ,

a r g

n

{\displaystyle {\mathit {arg}}{1},{\mathit {arg}}{2},...,{\mathit {arg}}_{n}}

are the arguments — natural numbers — that the sought function receives.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Ordered partitions step by step in the Python programming language

The provided Python code defines functions for partitioning a given set of numbers into subsets. Partitions are a fundamental concept in combinatorics, and these functions take a variable number of arguments, each representing the number of elements in the corresponding subset.

Here's a detailed breakdown of the code:

  1. The first function, partitions, uses a recursive approach to generate partitions. It takes as input a variable number of arguments, each representing the desired number of elements in the corresponding subset:

    • p is an inner function that implements the partition logic. It takes a set s of numbers and a list of arguments representing the desired subset sizes.
    • If there are no more arguments (i.e., all subsets have been filled), it returns a list containing an empty list, representing the trivial partition where each subset is empty.
    • Otherwise, it loops through all possible combinations of args[0] elements from the set s. For each combination, it removes those elements from s and recursively calls p on the remaining elements and the remaining arguments in the list.
    • The result is a list of lists, where each inner list represents a partition of the original set s.

  2. The second function, partitions, is a more concise version of the first function. It uses the itertools.combinations module to generate combinations and simplifies the recursive logic.

  3. The third function, partitions, takes a list of numbers xs and returns a list of all possible ordered partitions of xs.

    • go is an inner function that implements the recursive partition logic. It takes a set s of numbers, the total number of elements in xs, and a list ys of the desired subset sizes.
    • If ys is empty (i.e., all subsets have been filled), it returns a list containing an empty list, representing the trivial partition where each subset is empty.
    • Otherwise, it uses the choose function to generate all possible combinations of args[0] elements from s that sum up to ys[0]. For each combination, it removes those elements from s and recursively calls go on the remaining elements, the remaining total number of elements, and the remaining elements in ys.
    • The result is a list of lists, where each inner list represents an ordered partition of the original set xs.

  4. The choose function generates all possible combinations of m elements from a set of n elements, with the rest of the elements left as a separate list.

The main function at the end of the code provides a simple test of the partitions function, printing the partitions for two sets of numbers.

The fTable function is a helper function that formats the output of the partitions function as a table.

Overall, the provided code offers different ways to generate partitions of a set of numbers, each with its own strengths and efficiency characteristics. The specific choice of function to use depends on the specific requirements of your application.

Source code in the python programming language

from itertools import combinations

def partitions(*args):
    def p(s, *args):
        if not args: return [[]]
        res = []
        for c in combinations(s, args[0]):
            s0 = [x for x in s if x not in c]
            for r in p(s0, *args[1:]):
                res.append([c] + r)
        return res
    s = range(sum(args))
    return p(s, *args)

print partitions(2, 0, 2)


from itertools import combinations as comb

def partitions(*args):
    def minus(s1, s2): return [x for x in s1 if x not in s2]
    def p(s, *args):
        if not args: return [[]]
        return [[c] + r for c in comb(s, args[0]) for r in p(minus(s, c), *args[1:])]
    return p(range(1, sum(args) + 1), *args)

print partitions(2, 0, 2)


'''Ordered Partitions'''


# partitions :: [Int] -> [[[Int]]]
def partitions(xs):
    '''Ordered partitions of xs.'''
    n = sum(xs)

    def go(s, n, ys):
        return [
            [l] + r
            for (l, rest) in choose(s)(n)(ys[0])
            for r in go(rest, n - ys[0], ys[1:])
        ] if ys else [[]]
    return go(enumFromTo(1)(n), n, xs)


# choose :: [Int] -> Int -> Int -> [([Int], [Int])]
def choose(xs):
    '''(m items chosen from n items, the rest)'''
    def go(xs, n, m):
        f = cons(xs[0])
        choice = choose(xs[1:])(n - 1)
        return [([], xs)] if 0 == m else (
            [(xs, [])] if n == m else (
                [first(f)(x) for x in choice(m - 1)] +
                [second(f)(x) for x in choice(m)]
            )
        )
    return lambda n: lambda m: go(xs, n, m)


# TEST ----------------------------------------------------
# main :: IO ()
def main():
    '''Tests of the partitions function'''

    f = partitions
    print(
        fTable(main.__doc__ + ':')(
            lambda x: '\n' + f.__name__ + '(' + repr(x) + ')'
        )(
            lambda ps: '\n\n' + '\n'.join(
                '    ' + repr(p) for p in ps
            )
        )(f)([
            [2, 0, 2],
            [1, 1, 1]
        ])
    )


# DISPLAY -------------------------------------------------

# fTable :: String -> (a -> String) ->
#                     (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
    '''Heading -> x display function -> fx display function ->
                     f -> xs -> tabular string.
    '''
    def go(xShow, fxShow, f, xs):
        ys = [xShow(x) for x in xs]
        w = max(map(len, ys))
        return s + '\n' + '\n'.join(map(
            lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
            xs, ys
        ))
    return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
        xShow, fxShow, f, xs
    )


# GENERIC -------------------------------------------------

# cons :: a -> [a] -> [a]
def cons(x):
    '''Construction of a list from x as head,
       and xs as tail.
    '''
    return lambda xs: [x] + xs


# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
    '''Integer enumeration from m to n.'''
    return lambda n: list(range(m, 1 + n))


# first :: (a -> b) -> ((a, c) -> (b, c))
def first(f):
    '''A simple function lifted to a function over a tuple,
       with f applied only the first of two values.
    '''
    return lambda xy: (f(xy[0]), xy[1])


# second :: (a -> b) -> ((c, a) -> (c, b))
def second(f):
    '''A simple function lifted to a function over a tuple,
       with f applied only the second of two values.
    '''
    return lambda xy: (xy[0], f(xy[1]))


# MAIN ---
if __name__ == '__main__':
    main()

You may also check:How to resolve the algorithm Rot-13 step by step in the MUMPS programming language
You may also check:How to resolve the algorithm Chernick's Carmichael numbers step by step in the Nim programming language
You may also check:How to resolve the algorithm 21 game step by step in the Scala programming language
You may also check:How to resolve the algorithm Unbias a random generator step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Sum of squares step by step in the Smalltalk programming language