Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

""" 

Restricted growth arrays 

 

These combinatorial objects are in bijection with set partitions. 

""" 

#***************************************************************************** 

# Copyright (C) 2008 Mike Hansen <mhansen@gmail.com>, 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# 

# This code is distributed in the hope that it will be useful, 

# but WITHOUT ANY WARRANTY; without even the implied warranty of 

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 

# General Public License for more details. 

# 

# The full text of the GPL is available at: 

# 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from sage.combinat.combinat import bell_number 

from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets 

from sage.structure.parent import Parent 

from sage.structure.unique_representation import UniqueRepresentation 

import copy 

 

 

class RestrictedGrowthArrays(UniqueRepresentation, Parent): 

def __init__(self, n): 

""" 

EXAMPLES:: 

 

sage: from sage.combinat.restricted_growth import RestrictedGrowthArrays 

sage: R = RestrictedGrowthArrays(3) 

sage: R == loads(dumps(R)) 

True 

sage: TestSuite(R).run(skip=['_test_an_element', 

....: '_test_enumerated_set_contains', '_test_some_elements']) 

""" 

self._n = n 

self._name = "Restricted growth arrays of size %s" % n 

Parent.__init__(self, category=FiniteEnumeratedSets()) 

 

def __iter__(self): 

""" 

EXAMPLES:: 

 

sage: from sage.combinat.restricted_growth import RestrictedGrowthArrays 

sage: R = RestrictedGrowthArrays(3) 

sage: R.list() 

[[1, 0, 0], [2, 0, 1], [2, 1, 0], [2, 1, 1], [3, 1, 2]] 

""" 

n = self._n 

a = [1] + [0] * (n - 1) 

m = [0] + [1] * (n - 1) 

while True: 

yield copy.copy(a) 

# Search for maximum i with a[i] != m[i] 

i = n - 1 

while a[i] == m[i] and i >= 0: 

i -= 1 

if i == 0: 

break 

# Update arrays a and m 

a[i] += 1 

a[0] = a[i] + 1 if a[i] == m[i] else m[i] 

mi = a[0] 

for j in range(i + 1, n): 

a[j] = 0 

m[j] = mi 

 

def cardinality(self): 

""" 

EXAMPLES:: 

 

sage: from sage.combinat.restricted_growth import RestrictedGrowthArrays 

sage: R = RestrictedGrowthArrays(6) 

sage: R.cardinality() 

203 

""" 

return bell_number(self._n)