Partitionner au hasard un rectangle dans n plus petits rectangles

Question

Je recherche un algorithme qui peut partitionner un rectangle en n plus petits rectangles, au hasard. N sera petit (de l'ordre de 5-10 dans la plupart des cas). Il n'a pas besoin d'être uniformément au hasard, mais à tout le moins, j'aimerais éviter les algorithmes qui excluent complètement des classes intéressantes de partitions.

Un algorithme que j'ai rencontré plusieurs fois (y compris un question sur math.se sur le nombre de façons de faire n partitions), consiste à diviser au hasard le rectangle en deux en dessinant une ligne horizontale ou verticale, puis faites la même chose récursive aux rectangles plus petits qui en résultent jusqu'à ce que vous obteniez ce que vous voulez .

L'astuce ici est que bien que vous puissiez obtenir un certain nombre de partitions différentes en utilisant ce schéma:

Il existe certaines façons de diviser un rectangle en rectangles plus petits que cette méthode ne produira jamais:

Vous pouvez facilement voir que le partitionnement de division et de conquis ne générera jamais ce qui précède, car il n'y a pas de ligne qui pourrait être la première coupe, car aucune ligne droite unique ne divise tout le carré en deux rectangles plus petits.

Donc, fondamentalement, je recherche un algorithme pour diviser au hasard un rectangle en n plus petits rectangles, où les résultats répondent aux critères suivants:

• Partitionné dans exactement n plus petits rectangles
• Tout doit être un rectangle (pas de formes L, etc.)
• Il ne reste plus d'espace vide

L'algorithme dans son ensemble devrait répondre aux critères suivants:

• Il n'y a pas de partitionnement valide que l'algorithme est incapable de produire
• Peut être biaisé vers certains types de configurations, bien que moins le biais est le mieux.
• Fonctionne de préférence avec des indices entiers.
• Ne fonctionne pas en générant toutes les partitions possibles, puis en choisissant une au hasard.

Je me fiche beaucoup de la complexité asymptotique, car je vais travailler avec de petits nombres.