Trouver des facteurs de sous-ensemble

14

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 , 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

*                -> *
*.*.*            -> *, *.*.*
*.*.*.*          -> *, *.*, *...*, *.*.*.*
******           -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.**  -> *, *...**.**, *.....*, *...*****.**.**
Post Rock Garf Hunter
la source
Si nous prenons l'ensemble comme une liste de nombres (par exemple [1,3,5,7]pour *.*.*.*) pouvons-nous supposer qu'il est trié?
Martin Ender
1
Est-ce que cela revient à trouver des diviseurs de polynômes dont les coefficients sont limités à 0 et 1?
xnor
1
@xnor, je ne suis pas sûr. Si *.*.*= x+x^2+x^4, alors 1+x+x^2= ***serait un diviseur, non? x+x^2+x^4 = (1-x+x^2)(1+x+x^2)
mbomb007
1
@JonathanAllan Pour vos exemples, *est répertorié comme un facteur qui représente le même sous-ensemble que *.ou *...
Martin Ender
1
@JonathanAllan Il indique la sortie de tous les ensembles, pas la sortie de toutes les représentations ASCII des ensembles valides.
Martin Ender

Réponses:

3

Mathematica, 71 68 octets

#&@@@Cases[(s=Subsets)@s@#,x_/;Sort[Join@@x]==#&&Equal@@(#&@@@x-x)]&

Entrer 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).

Martin Ender
la source
2

Gelée , 12 octets

;÷@DỊȦ
ÆDçÐf

Les entrées et sorties utilisent 1et 0au lieu de *et ..

Essayez-le en ligne!

Comment ça fonctionne

ÆDçÐf   Main link. Argument: n (integer with decimal digits 1 and 0)

ÆD      Compute all divisors of n.
  çÐf   Filter; call the helper link with left argument d and right argument n for
        all divisors d of n. Return the array of d's for which the helper link
        returns a truthy value.


;÷@DỊȦ  Helper link. Left argument: d. Right argument: n

 ÷@     Divide n by d.
;       Concatenate, yielding [d, n÷d].
   D    Decimal; convert both integers in the pair to base 10.
    Ị   Insignificant; map 1 and 0 to 1, all other positive integers to 0.
     Ȧ  All; return 1 iff the result contains no zeroes.
Dennis
la source