partitions.py

Aller à la documentation de ce fichier.

#!/usr/bin/env python
# -*- coding: latin-1 -*-
##\package DSPython.partitions Partitions de naturels
#!!! Work in progress !!!
#
# Cf. \htmlonly <a href="http://www.opimedia.be/partitions/" target="_blank">
#   <tt>http://www.opimedia.be/partitions/</tt></a>\endhtmlonly

##\file
# Partitions de naturels
# !!! Work in progress !!!
#
# Cf. \htmlonly <a href="http://www.opimedia.be/partitions/" target="_blank">
#   <tt>http://www.opimedia.be/partitions/</tt></a>\endhtmlonly

# (c) Olivier Pirson --- DragonSoft
# http://www.opimedia.be/DS/
# Débuté le 20 août 2006
####################################
from __future__ import print_function

## Date du dernier changement pour ce module
VERSION = 'partitions --- 2010 April 12'

import array

import DSPython
import DSPython.natural as natural
import DSPython.integer as integer



# ###########
# Fonctions #
#############
## Compositions de n
def compos(n):
    """Renvoie la liste des compositions de n

    Pre: n: naturel

    Result: séquence ???

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    p = []
    l = []
    m = n
    s = 0
    #???print(n, ':', end='')
    while len(l) < n:
        m = min(n - s, m)
        #???print(m, end='')
        if m > 0:
            #???print('+', end='')
            s += m
            l.append(m)
            #???print(l, end='')
        else:
            #???print('-', end='')
            p.append(tuple(l))
            if len(l) > 1:
                s -= l.pop()
                l.append(l.pop() + 1)
                s += 1
            else:
                break
    p.append(tuple(l))
    #???print(p)
    return p


## Compositions de n de k termes
def compos_k(n, k):
    """Renvoie la liste des compositions de n de k termes

    Pre: n: naturel
         k: naturel ???

    Result: séquence ???

    O(n, k) = ..."""
    assert DSPython.natural_is(n), n
    assert DSPython.natural_is(k), k

    if 0 < k <= n:
        a = array.array('L', [1 for i in range(k)])  # composition de k termes
        a[0] = n - k + 1
        for i in range(n - k):
            pass ##???
        return [tuple(a)]
    elif k == 0 == n:
        return [()]
    else:
        return []

    return (integer.binom(n - 1, k - 1) if n >= k
            else 0)


## Nombre de compositions de n
def compos_nb(n):
    """Renvoie le nombre de compositions de n

    Pre: n: naturel

    Result: naturel

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    return (natural.pow2(n - 1) if n > 0
            else 1)



# ######\cond MAINTEST
# Main #
########
if __name__ == '__main__':
    def main_test():
        """Test du module"""
        import sys

        import DSPython.debug as debug

        debug.test_begin(VERSION, __debug__)

        print('compos()...', end=''); sys.stdout.flush()
        assert compos(0) == [()], compos(0)
        assert compos(1) == [(1,)], compos(1)
        #assert compos(2) == [(2,), (1, 1)], compos(2)
        #assert compos(3) == [(3,), (2, 1), (1, 2), (1, 1, 1)], compos(3)
        print('???', end='')
        print('ok'); sys.stdout.flush()


        print('compos_k()...', end=''); sys.stdout.flush()
        assert compos_k(0, 0) == [()], compos_k(0, 0)
        for n in range(1, 100):
            assert compos_k(n, 0) == [], (n, compos_k(n, 0))
            assert compos_k(n, 1) == [(n, )], (n, compos_k(n, 1))
        #???assert compos_k(3, 2) == [(2, 1), (1, 2)], compos_k(3, 2)
        print('???', end='')
        print('ok'); sys.stdout.flush()


##        print('compos_k_nb()...', end=''); sys.stdout.flush()
##        assert compos_k_nb(0, 0) == 1, compos_k_nb(0, 0)
##        for n in range(1, 100):
##            assert compos_k_nb(n, 0) == 0, (n, compos_k_nb(n, 0))
##            assert compos_k_nb(n, 1) == 1, (n, compos_k_nb(n, 1))
##            assert compos_k_nb(n, n) == 1, (n, compos_k_nb(n, n))
##            for k in range(1, 50):
##                assert compos_k_nb(n, n+k) == 0, (n, k, compos_k_nb(n, n+k))
##        assert compos_k_nb(3, 2) == 2, compos_k_nb(3, 2)
##        assert compos_k_nb(4, 2) == 3, compos_k_nb(4, 2)
##        assert compos_k_nb(4, 3) == 3, compos_k_nb(4, 3)
##        for n in range(1, 50):
##            s = 0
##            for k in range(n+1):
##                s += compos_k_nb(n, k)
##            assert s == compos_nb(n), (n, s, compos_nb(n))
##        print('???', end='')
##        print('ok'); sys.stdout.flush()


        print('compos_nb()...', end=''); sys.stdout.flush()
        assert compos_nb(0) == 1, compos_nb(0)
        assert compos_nb(1) == 1, compos_nb(1)
        assert compos_nb(2) == 2, compos_nb(2)
        assert compos_nb(3) == 4, compos_nb(3)
        for n in range(1, 100):
            assert compos_nb(n) == 2**(n - 1), (n, compos_nb(n))
        print('???', end='')
        print('ok'); sys.stdout.flush()
        debug.test_end()

    main_test()
##\endcond MAINTEST