Voir le titre pour question. La seule autre limitation est que les plus petits rectangles doivent être formés en plongeant de plus gros rectangles en deux. J'ai joint le résultat pour n = 3 et n = 4 ci-dessous. Espérons que cela suffira à expliquer le sens de mes questions.
Actuellement, j'ai un algorithme récursif inefficace qui divise chaque rectangle horizontalement et verticalement et garde une trace de toutes les combinaisons possibles dans une matrice. Je n'aime pas cet algorithme. C'est une période polynomiale, semble inutilement compliqué et me donne des doublons, comme on le voit dans la photo n = 4 (indice: recherchez quatre quadrants égaux) P>
Je me demandais s'il y avait une meilleure solution à ce sujet? J'échappais avec l'utilisation d'un arbre de 4 ary (où chaque enfant obtient une pièce verticale ou horizontale) et je suis capable de construire l'arbre mais de tirer toutes les combinaisons possibles de l'arbre semble m'élorer. Je posterai le code de la plaque de la chaudière arbre ci-dessous: P>
class Node:
#value is an tuple (x0,y0,x1,y1)
def __init__(self, value):
self.horizontal = []
self.vertical = []
self.value = value
def createTree(depth, currDepth, node):
if currDepth == depth:
return
node.horizontal.append(Node(getLeftRect(node.value)))
node.horizontal.append(Node(getRightRect(node.value)))
node.vertical.append(Node(getTopRect(node.value)))
node.vertical.append(Node(getBotRect(node.value)))
createTree(depth, currDepth+1, node.horizontal[0])
createTree(depth, currDepth+1, node.horizontal[1])
createTree(depth, currDepth+1, node.vertical[0])
createTree(depth, currDepth+1, node.vertical[1])
5 Réponses :
idée d'un algorithme de construction récursif ou d'arbres qui évite les doublons:
Vous commencez avec un rectangle et plusieurs fois, il doit être divisé. Divisez-le dans les deux sens et diminuez le nombre par un, puis pour chaque division (verticale et horizontale), partitionnez le nombre sur les deux parties.
Cette méthode entraîne 39 divisions lors de la division en 4 parties (et 1 duplicata).
Le seul doublon que je n'ai pas été capable d'éviter, c'est la croix. En utilisant cette méthode, chaque fois que vous avez un rectangle qui doit être divisé de 3 fois plus de 3 ou plusieurs fois, vous allez courir dans la croix deux fois. Donc, vous devrez ajouter un chèque supplémentaire pour cela.
Vous remarquerez également que les 4 groupes de 8 solutions résultant d'un partitionnement initial Il semble que les duplicats deviennent plus difficiles à éviter avec cette méthode que je pensais d'abord. Si vous ajoutez 2 autres divisions, l'apparemment très différent Comme David Eisenstat mentionne dans sa réponse, vous pouvez éviter les doubles en croix en permettant à des deux moitiés d'un rectangle d'être divisé en une seule commande (par ex. premier vertical, puis horizontal) mais pas l'autre. Cela signifie que lors du traitement d'un rectangle, vous devez être conscient de son "autre moitié", et de savoir si et comment la moitié a été divisée; Donc, cela complique le code nécessaire pour utiliser cette méthode. 2,0 sont des rotations de 90 °, 180 ° et 270 ° les uns des autres. Et les 2 groupes de 4 solutions résultant d'un partitionnement initial 1,1 sont des rotations de 90 ° les unes des autres. Vous pouvez donc résoudre un seul groupe, puis faire pivoter pour obtenir toutes les solutions.
L3 R1 et T2 B2 Les options principales conduisent à plusieurs duplicats 4 étapes plus loin:
Je faisais quelque chose de très semblable à votre méthode! Comment évitez-vous cependant les 2 autres doublons? Si nous supposons n = 4, vous devriez obtenir 2 combinaisons avec des quadrants égaux lorsque vous commencez par diviser horizontalement, et 2 lorsque vous commencez par diviser verticalement. Ou avez-je mal compris votre méthode?
@Sid, j'ai édité l'image, car je sautais une étape. Vous verrez que 2 des 6 options principales ne conduisent que 2, puis 4, au lieu de 4, puis 8, solutions. C'est là que vos 8 doublons supplémentaires seraient.
Une stratégie est que lorsque nous coupons verticalement, ne laissez pas à la fois la moitié gauche et la moitié droite possédant une coupe horizontale. Cela implique une analyse de cas.
dans Python 3, nous avons d'abord des types de données pour représenter des rectangles subdivisés. P>
def generate(n):
assert isinstance(n, int) and n >= 0
yield from generate_with_horizontal(n)
yield from generate_without_horizontal(n)
def generate_with_horizontal(n):
assert isinstance(n, int) and n >= 0
for k in range(n):
for top in generate(k):
for bottom in generate(n - 1 - k):
yield H(top, bottom)
def generate_without_horizontal(n):
assert isinstance(n, int) and n >= 0
if n == 0:
yield W()
for k in range(n):
for left in generate_with_horizontal(k):
for right in generate_without_horizontal(n - 1 - k):
yield V(left, right)
for left in generate_without_horizontal(k):
for right in generate(n - 1 - k):
yield V(left, right)
C'est incroyable comment vous avez trouvé un tel code de recherche! Il m'a fallu un moment pour l'obtenir (je ne suis pas encore très familier avec Python / Generators) mais je reçois le gist de la logique. Merci!
Cela évite-t-il des doublons après 5, 7, 9 ... Étapes aussi? Je viens de me rendre compte que la croix après 3 étapes n'est que la première d'un certain nombre de problèmes. Voir l'image supplémentaire dans ma réponse.
@ m69 oui. Essentiellement, nous définissons un ordre canonique dans lequel faire des coupes, où nous faisons une coupure horizontale si nous le pouvons et une coupe verticale autrement. Le point de générate_without_horizontal est qu'il assure au moins une dalle verticale ininterrompue, de justifier la coupe verticale à la racine de l'arbre coupé.
Pourriez-vous poster le nombre de solutions uniques pour des rectangles jusqu'à 8 rectangles?
@ M69 [1, 2, 8, 39, 212, 1232, 7492, 47082, 303336, 1992826]
OK, il semble donc qu'il y a quelques façons de générer toutes les possibilités non isomorphes, alors ma suggestion serait:
La chose est, à moins que vous n'ayez besoin de résultat pour les grandes intrants (disons 6-10), vous ne voulez pas les générer à la volée. Même si vous souhaitez montrer les résultats de cette taille de partition, il serait sûrement beaucoup plus grand que possible d'afficher utilement à l'utilisateur!
Cela dit, si vous souhaitez générer des représentants non isomorphes de ces structures, il existe des recherches intéressantes sur "Duals slicables" - voir par exemple cette thèse de maîtrise par Vincent Kusters. Notez que vos structures sont plus générales car elles incluent des partitions qui se rencontrent à quatre rejoins.
Voici une récursion de Python qui enregistre l'arborescence comme un dictionnaire où les enfants sont indexés comme Résultats pour 2i et 2i + 1 . J'ai essayé de mettre en œuvre la suggestion de David Eisenstat sur l'évite d'une fraction horizontale des deux côtés d'une fraction verticale (le nombre de résultats semble correspondre à ceux qu'il a fournis dans les commentaires). f (4) :
Ce n'est pas une réponse directe à votre question, mais vous devez le considérer:
Soyez très prudent tout en utilisant un algorithme récursif pour compter le nombre de partitions pour N> 4. La raison en est que nous pouvons avoir des partitions dans lesquelles la fusion de deux rectangules ne finit pas dans une autre rectangulaire. Par exemple, pour cinq partitions, considérons les éléments suivants:
Je pense que les algorithmes suggèrent ci-dessus manquer toutes partitions similaires à celle-ci.
Vous obtiendrez plus de vues de votre question si vous ajoutez la balise de langue.
Il existe un nombre infini de façons qu'un rectangle puisse être divisé en
N plus petits rectangles. Quelles sont les autres restrictions?@Jimmischel a mis à jour la question. Merci d'avoir fait remarquer cela. S'il vous plaît voir les images ci-jointes pour un meilleur sens de ce que je voulais dire
Vous voulez réellement les visuels, non? Pas le compte de combien de façons?
@ גגעבברקן Oui, c'est correct. J'ai besoin des coordonnées des rectangles résultants pour chaque permutation afin que je puisse les afficher sur mon ui
Vos exemples semblent être des carrés mais vous voulez dire n'importe quel type de rectangle?
Oui, tout type de rectangle devrait fonctionner. Un carré est un type particulier de rectangle après tout
BTW math.stackexchange.com/questions/1116/...
(pourrait être un point muet, donné la bonne réponse de David, mais j'ai ajouté ma propre version récursive.)