14
\$\begingroup\$

Let's imagine we have a finite set of positive integers. This set can be represented as a line of dots where each integer present in the set is filled in like a scantron or punch card. For example the set {1,3,4,6} could be represented as:

*.**.*

* represents a member of our set and . represents an integer that is not a member oft he set.

These sets have "factors". Loosely x is a factor of y if y can be built out of copies of x. More rigorously our definition of factor is as follows:

  • x is a factor of y if and only if y is the union of a number of disjoint sets, all of which are x with an offset.

We would call *.* a factor of *.**.* because it is quite clearly made up of two copies of *.* put end to end.

*.**.*
------
*.*...
...*.*

Factors don't have to be end to end, we would also say that *.* is a factor of *.*.*.*

*.*.*.*
-------
*.*....
....*.*

Factors can also overlap. This means *.* is also a factor of ****

****
----
*.*.
.*.*

However a number cannot be covered by a factor more than once. For example *.* is not a factor of *.*.*.


Here is a more complicated example:

 *..*.**..***.*.*

This has *..*.* as a factor. You can see that below where I have lined up the three instances of *..*.*.

*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*

Task

Given a set by any reasonable representation output all the sets that are factors of the input.

You may index by any value, (that is you may select a smallest number that can be present in the input). You may also assume that the input set will always contain that smallest value.

This is a question so you should aim to do this in as few bytes as possible.

Test Cases

These test cases were done by hand, there may be a mistake or two on the larger ones

*                -> *
*.*.*            -> *, *.*.*
*.*.*.*          -> *, *.*, *...*, *.*.*.*
******           -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.**  -> *, *...**.**, *.....*, *...*****.**.**
\$\endgroup\$
  • \$\begingroup\$ If we take the set as a list of numbers (e.g. [1,3,5,7] for *.*.*.*) can we assume that it's sorted? \$\endgroup\$ – Martin Ender Jun 2 '17 at 13:25
  • 1
    \$\begingroup\$ Is this equivalent to finding divisors of polynomials whose coefficients are restricted to 0 and 1? \$\endgroup\$ – xnor Jun 2 '17 at 13:28
  • 1
    \$\begingroup\$ @xnor I'm not sure. If *.*.* = x+x^2+x^4, then 1+x+x^2 = *** would be a divisor, right? x+x^2+x^4 = (1-x+x^2)(1+x+x^2) \$\endgroup\$ – mbomb007 Jun 2 '17 at 13:33
  • 1
    \$\begingroup\$ @JonathanAllan For your examples, * is listed as a factor which represents the same subset as *. or *... \$\endgroup\$ – Martin Ender Jun 2 '17 at 13:35
  • 1
    \$\begingroup\$ @JonathanAllan It says output all sets, not output all ASCII representations of the valid sets. \$\endgroup\$ – Martin Ender Jun 2 '17 at 13:48
3
\$\begingroup\$

Mathematica, 71 68 bytes

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

Input as {1,3,5,7} (sorted) and output as {{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. The function will throw a bunch of messages.

This is O(22Nope) (where N is the length of the input and o=p=e=1...). It generates all subsets of subsets, then selects those that result in the input send when joined together (ensuring we're only considering partitions) and where all elements are the same if we subtract the smallest value of each subset).

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Jelly, 12 bytes

;÷@DỊȦ
ÆDçÐf

Input and output use 1 and 0 instead of * and ..

Try it online!

How it works

Æ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.
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.