10 added 38 characters in body
source | link
def ordered_partitionsordered_compositions(n):
  """
  Yield all ordered partitionscompositions of n.
  """
  if n == 1:
    yield [1]
  else:
    for partitioncomposition in ordered_partitionsordered_compositions(n - 1):
      partition[composition[-1] += 1 # add 1
      yield partitioncomposition
      partition[composition[-1] -= 1 # remove the added 1
      partitioncomposition.append(1) # other way to add 1
      yield partitioncomposition
      partitioncomposition.pop() # remove added 1

for partitioncomposition in ordered_partitionsordered_compositions(4):
   print(partitioncomposition)

Note that this mutates partitionscompositions (towers) after yielding them (this is why $O(2^n)$ is possible), so if you want to make a list from it, you'll have to copy each partitioncomposition.

This algorithm can be found by noting that each partitioncomposition of $n$ is a partitioncomposition of $n-1$, with a $1$ added to the end, or with a $1$ added to the last number.

the partitionscompositions of 2 are:

and the partitionscompositions of 3 are:

This algorithm could also be implemented by keeping a bool array of length $n-1$ (representing appending to the list, or adding to the last element), and a int vector (the partitioncomposition). The bool array would start all false, and the vector containing $n$.

def ordered_partitions(n):
  """
  Yield all ordered partitions of n.
  """
  if n == 1:
    yield [1]
  else:
    for partition in ordered_partitions(n - 1):
      partition[-1] += 1 # add 1
      yield partition
      partition[-1] -= 1 # remove the added 1
      partition.append(1) # other way to add 1
      yield partition
      partition.pop() # remove added 1

for partition in ordered_partitions(4):
   print(partition)

Note that this mutates partitions (towers) after yielding them (this is why $O(2^n)$ is possible), so if you want to make a list from it, you'll have to copy each partition.

This algorithm can be found by noting that each partition of $n$ is a partition of $n-1$, with a $1$ added to the end, or with a $1$ added to the last number.

the partitions of 2 are:

and the partitions of 3 are:

This algorithm could also be implemented by keeping a bool array of length $n-1$ (representing appending to the list, or adding to the last element), and a int vector (the partition). The bool array would start all false, and the vector containing $n$.

def ordered_compositions(n):
  """
  Yield all ordered compositions of n.
  """
  if n == 1:
    yield [1]
  else:
    for composition in ordered_compositions(n - 1):
      composition[-1] += 1 # add 1
      yield composition
      composition[-1] -= 1 # remove the added 1
      composition.append(1) # other way to add 1
      yield composition
      composition.pop() # remove added 1

for composition in ordered_compositions(4):
   print(composition)

Note that this mutates compositions (towers) after yielding them (this is why $O(2^n)$ is possible), so if you want to make a list from it, you'll have to copy each composition.

This algorithm can be found by noting that each composition of $n$ is a composition of $n-1$, with a $1$ added to the end, or with $1$ added to the last number.

the compositions of 2 are:

and the compositions of 3 are:

This algorithm could also be implemented by keeping a bool array of length $n-1$ (representing appending to the list, or adding to the last element), and a int vector (the composition). The bool array would start all false, and the vector containing $n$.

9 edited body
source | link

This algorithm could also be implemented by keeping a bool array of length $n-1$ (representing appending to the list, or adding to the last element), and a int vector (the partition). The bool array would start all false, and the vector containing $n$.

This could also be implemented by keeping a bool array of length $n-1$ (representing appending to the list, or adding to the last element), and a int vector (the partition). The bool array would start all false, and the vector containing $n$.

This algorithm could also be implemented by keeping a bool array of length $n-1$ (representing appending to the list, or adding to the last element), and a int vector (the partition). The bool array would start all false, and the vector containing $n$.

8 edited body
source | link
def ordered_partitions(n):
  """
  Yield all ordered partitions of n.
  """
  if n == 1:
    yield [1]
  else:
    for partition in ordered_partitions(n - 1):
      partition[-1] += 1 # add 1
      yield partition
      partition[-1] -= 1 # remove the added 1
      partition.append(1) # other way to add 1
      yield partition
      partition.pop() # remove added 1

for partition in ordered_partitions(34):
   print(partition)
def ordered_partitions(n):
  """
  Yield all ordered partitions of n.
  """
  if n == 1:
    yield [1]
  else:
    for partition in ordered_partitions(n - 1):
      partition[-1] += 1 # add 1
      yield partition
      partition[-1] -= 1 # remove the added 1
      partition.append(1) # other way to add 1
      yield partition
      partition.pop() # remove added 1

for partition in ordered_partitions(3):
   print(partition)
def ordered_partitions(n):
  """
  Yield all ordered partitions of n.
  """
  if n == 1:
    yield [1]
  else:
    for partition in ordered_partitions(n - 1):
      partition[-1] += 1 # add 1
      yield partition
      partition[-1] -= 1 # remove the added 1
      partition.append(1) # other way to add 1
      yield partition
      partition.pop() # remove added 1

for partition in ordered_partitions(4):
   print(partition)
7
source | link
6
source | link
5 added 282 characters in body
source | link
4 added 282 characters in body
source | link
3 added 282 characters in body
source | link
2 added 282 characters in body
source | link
    Post Undeleted by internet_user
    Post Deleted by internet_user
1
source | link