Imaginons que nous ayons un ensemble fini d'entiers positifs. Cet ensemble peut être représenté comme une ligne de points où chaque entier présent dans l'ensemble est rempli comme un scantron ou une carte perforée . Par exemple, l'ensemble {1,3,4,6}pourrait être représenté comme suit:
*.**.*
*représente un membre de notre ensemble et .représente un entier qui n'est pas membre de l'ensemble.
Ces ensembles ont des "facteurs". Lâchement x est un facteur de y si y peut être construit à partir de copies de x. Plus rigoureusement, notre définition du facteur est la suivante:
- x est un facteur de y si et seulement si y est l'union d'un certain nombre d' ensembles disjoints , qui sont tous x avec un décalage.
Nous appellerions *.*un facteur de *.**.*car il est très clairement constitué de deux exemplaires de *.*bout en bout.
*.**.*
------
*.*...
...*.*
Les facteurs ne doivent pas être de bout en bout, nous dirions aussi que *.*c'est un facteur de*.*.*.*
*.*.*.*
-------
*.*....
....*.*
Les facteurs peuvent également se chevaucher. Cela signifie *.*également****
****
----
*.*.
.*.*
Cependant, un nombre ne peut pas être couvert par un facteur plus d'une fois. Par exemple, *.*n'est pas un facteur de *.*.*.
Voici un exemple plus compliqué:
*..*.**..***.*.*
Cela a *..*.*un facteur. Vous pouvez le voir ci-dessous où j'ai aligné les trois instances de *..*.*.
*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*
Tâche
Étant donné un ensemble par n'importe quelle représentation raisonnable, tous les ensembles qui sont des facteurs de l'entrée.
Vous pouvez indexer par n'importe quelle valeur (c'est-à-dire que vous pouvez sélectionner le plus petit nombre pouvant être présent dans l'entrée). Vous pouvez également supposer que l'ensemble d'entrée contiendra toujours cette plus petite valeur.
Il s'agit d'une question de code-golf , vous devez donc viser à le faire dans le moins d'octets possible.
Cas de test
Ces cas de test ont été faits à la main, il peut y avoir une erreur ou deux sur les plus grands
* -> *
*.*.* -> *, *.*.*
*.*.*.* -> *, *.*, *...*, *.*.*.*
****** -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.** -> *, *...**.**, *.....*, *...*****.**.**
la source
[1,3,5,7]pour*.*.*.*) pouvons-nous supposer qu'il est trié?*.*.*=x+x^2+x^4, alors1+x+x^2=***serait un diviseur, non?x+x^2+x^4 = (1-x+x^2)(1+x+x^2)*est répertorié comme un facteur qui représente le même sous-ensemble que*.ou*...Réponses:
Mathematica,
7168 octetsEntrer comme
{1,3,5,7}(trié) et sortir comme{{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. La fonction lancera un tas de messages.Il s'agit de O (2 2 Nope ) (où N est la longueur de l'entrée et o = p = e = 1 ...). Il génère tous les sous-ensembles de sous-ensembles, puis sélectionne ceux qui entraînent l'envoi d'entrée lorsqu'ils sont réunis (en veillant à ne considérer que les partitions) et où tous les éléments sont les mêmes si nous soustrayons la plus petite valeur de chaque sous-ensemble).
la source
Gelée , 12 octets
Les entrées et sorties utilisent
1et0au lieu de*et..Essayez-le en ligne!
Comment ça fonctionne
la source