21
\$\begingroup\$

A superpowerset (analogous to superpermutation) on \$n\$ symbols is a string over the alphabet \$\{1,2,...,n\}\$ such that every subset of \$\{1,2,...,n\}\$ appears as a substring (in some order). For instance, 12342413 is a superpowerset on four symbols because it contains 1, 2, 3, 4, 12, 13, 41, 23, 24, 34, 123, 241, 413, 234, 1234.

The lengths of the shortest such strings and some examples are given in this sequence: A348574

The Challenge

Given a string composed of \$n\$ unique symbols (and, optionally, \$n\$), output whether it is a superpowerset on \$n\$ symbols.

Rules

  • This is so the shortest answer in bytes wins.

  • Assume only valid input will be given.

  • Assume \$n\$ is greater than \$0\$

  • Input and output can assume whatever form is most convenient, e.g. the series of symbols can be a string, a list, an integer, a set of n bitmasks, etc, so long as it is indicated in the answer. Additionally, anything may be used as a symbol provided it is distinct from all the other symbols.

Test Cases

In: 1234
Out: False

In: 1
Out: True

In: 11111111
Out: True

In: 123
Out: False

In: 1234512413
Out: False

In: 12342413
Out: True

In: 123424133333333
Out: True

In: 1234567214573126431523674256147325716357
Out: True

In: 122331
Out: False
\$\endgroup\$
12
  • 4
    \$\begingroup\$ Welcome to Code Golf, and nice challenge! \$\endgroup\$ Feb 7 at 21:02
  • 1
    \$\begingroup\$ I think a few more test cases, especially ones which give false outputs, would be helpful. \$\endgroup\$
    – pxeger
    Feb 7 at 21:05
  • 1
    \$\begingroup\$ May we assume that the symbols are \$1\dots9\$? \$\endgroup\$
    – Arnauld
    Feb 7 at 23:57
  • 1
    \$\begingroup\$ May I freely choose symbols used? Or is 33333 a valid truthy testcase? \$\endgroup\$
    – tsh
    Feb 8 at 1:43
  • 1
    \$\begingroup\$ Suggested test case: 122331 (false). \$\endgroup\$
    – Arnauld
    Feb 8 at 9:00

14 Answers 14

5
\$\begingroup\$

Jelly, 9 bytes

ŒPḊfƑɓẆṢ€

A dyadic Link accepting the alphabet size, N, on the left and the candidate string, S, on the right as a list of integers that yields 1 if the string is a superpowerset of that alphabet size.

Try it online!

How?

ŒPḊfƑɓẆṢ€ - Link: integer, N; list of integers, S
ŒP        - powerset of [1..N]
  Ḋ       - dequeue - removes the empty list
     ɓ    - new chain with swapped arguments:
      Ẇ   -   all sublists of S
       Ṣ€ -   sort each
    Ƒ     - is the dequeued powerset invariant under:
   f      -   filter keep the sorted sublists
\$\endgroup\$
1
  • 1
    \$\begingroup\$ @Arnauld, no I left 3 in the argument from trying out some other inputs; I have changed it back to 4. Thanks! \$\endgroup\$ Feb 8 at 12:31
4
\$\begingroup\$

Python, 90 bytes

lambda i,n:f(*i)+2>>2**n
f=lambda a,*i,k=0:1<<(l:=k|1<<a-1)|(i>()and(l>k)*f(*i,k=l)|f(*i))

Attempt This Online!

Takes a list of integers i and the integer n as arguments. Uses bitmasks to avoid lengthy frozensets.

Using one less layer of bitmasks might be a bit clearer, but costs a byte.

\$\endgroup\$
2
  • \$\begingroup\$ What truthy value can i have that is not greater than ()? \$\endgroup\$
    – Neil
    Feb 8 at 10:33
  • \$\begingroup\$ @Neil i is always a tuple, so there is no such value. But I want the expression (i>()and ...) to evaluate to False/0 if i is empty \$\endgroup\$
    – ovs
    Feb 8 at 10:35
4
\$\begingroup\$

Husk, 11 10 8 7 bytes

Edit: -2 bytes after inspiration from caird coinheringaahing, and then -1 byte by stealing the I/O idea from emanresu A's answer

-ṁPQ¹Ṗu

Try it online!

Outputs a list of an empty list ([[]]) if a superpowerset, or a list containing nonempty lists otherwise.

      u       # Get uniqe elements of input,
     Ṗ        # and get all subsequences
-             # now remove from this
 ṁP           # all permutations of
   Q¹         # all contiguous sublists of the input.
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Just a possibility, but if Husk has an "is contiguous sub list of" builtin, and it works for the empty list, then you should be able to remove both the t and the Q. I'm not too familiar with Husk's builtin list tho \$\endgroup\$ Feb 8 at 6:32
  • \$\begingroup\$ @cairdcoinheringaahing - Thanks for the suggestion. The Husk does indeed have a subl function to do that (actually it's the same function applied to two lists), but I think that the problem is that each contiguous sublist needs to be sorted before checking for a match, since the subsets that we're checking might not be in the right order otherwise... \$\endgroup\$ Feb 8 at 7:21
  • \$\begingroup\$ @cairdcoinheringaahing - Thanks again: your suggestion prompted me to try swapping sorting for testing all permutations (see edits), which finally led to a different 2-byte golf... \$\endgroup\$ Feb 8 at 7:46
3
\$\begingroup\$

Jelly, 10 bytes

ŒPŒ!ẇ€SɗƇƑ

Try it online!

Takes \$n\$ on the left, and a list of integers up to \$n\$ on the right

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 41 bytes

Length[{}⋃Union/@Subsequences@#]==2^#2&

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 9 bytes

ÞSvs?Uṗ$F

Try it Online!

Returns a list containing the empty list (⟨ ⟨ ⟩ ⟩) for truthy and a list containing nonempty lists for falsy.

ÞS        # Sublists...
  vs      # Sort each
       $F # Remove from...
      ṗ   # Powerset of...
    ?U    # Unique symbols of input
\$\endgroup\$
1
  • \$\begingroup\$ Very clever use of I/O! I hope you'll take it as a compliment if I now steal that trick...! \$\endgroup\$ Feb 8 at 8:10
2
\$\begingroup\$

Wolfram Language (Mathematica), 84 bytes

And@@(Subsequences@s~ContainsAny~Permutations@#&/@Subsets@Union[s=IntegerDigits@#])&

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 83 76 bytes

->l,n{!(z=*1..n).uniq{|w|[*z.combination(w)]-l.each_cons(w).map(&:sort)}[1]}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 98 bytes

lambda i,s:len(f(i))>>s
f=lambda i,*t:i and{1,len(i)>len({*i})or frozenset(i),*f(*t,i[1:],i[:-1])}

Try it online!

Takes a list of numbers and the number of symbols.

In python, you can't have a set of sets, instead you have to use the immutable frozenset. The algorithm is quite simple, just check every substring. To do that, you can use the vararg-sublist trick, where f is called for every sublist of the input in length order. The recursion is stopped when we encounter the empty list. This means that if this is really a superpowerset, then the resulting set will contain \$2^s\$ elements (every subset, except the empty set plus a 1). We can then use a bitshift to check for that condition.

It's possible to replace frozenset(i) with (*{*i},) for -5 bytes, but I'm not sure if the order of the set expansion is well defined.

\$\endgroup\$
1
\$\begingroup\$

Factor + math.combinatorics math.unicode, 74 bytes

[ dup members all-subsets rest swap all-subseqs [ natural-sort ] map ⊂ ]

Try it online!

"Is the power set of the input's alphabet a subset of the sorted sub-sequences of the input?"

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES10), 86 bytes

Saved 14 bytes thanks to @tsh!

Expects an array of symbols. Returns \$0\$ or \$1\$.

a=>(g=a=>new Set(a).size)(a.flatMap(x=>p=[...p,y=1<<x].map(v=>v&y?0:v|y),p=[0]))>>g(a)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ a=>new Set(a.flatMap(x=>p=[...p,y=1<<x].map(v=>v&y?0:v|y),p=[0])).size>>new Set(a).size \$\endgroup\$
    – tsh
    Feb 8 at 2:17
  • \$\begingroup\$ new Set(...).size>>new Set(...).size -> g(...)>>g(...);g=a=>new Set(a).size \$\endgroup\$
    – tsh
    Feb 8 at 2:52
1
\$\begingroup\$

Japt v2.0a0, 12 bytes

â à eÈá d@øX

Try it

â         - unique elements
  à       - combinations
    eÈ    - all?
á           * permutations of that combination
  d@        * any?
    øX        in input U
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 53 bytes

W⁻⪪θ¹υ⊞υ⌊ι≔⟦⟧ηFLθFE⊕ι✂θκ⊕ιF⬤κ⁼¹№κλ⊞ηΣX²Eκ⌕υμ¬⁻…¹X²Lυη

Try it online! Link is to verbose version of code. Takes a string as input and outputs a Charcoal boolean, i.e. - for a superpowerset, nothing if not. Explanation:

W⁻⪪θ¹υ⊞υ⌊ι

Get the unique elements of the input.

≔⟦⟧η

Start collecting integers representing sets of unique elements.

FLθFE⊕ι✂θκ⊕ι

For each substring, ...

F⬤κ⁼¹№κλ

... if this substring only contains unique elements, then ...

⊞ηΣX²Eκ⌕υμ

... collect a bitmask of the unique elements.

¬⁻…¹X²Lυη

Check that all possible bitmasks were collected.

34 bytes for a specific input format:

FLηFE⊕ι✂ηκ⊕ιF⬤κ⁼¹№κλ⊞ηΣX²κ¬⁻…¹X²θη

Try it online! Link is to verbose version of code. Uses the same algorithm, but takes an integer n and a list of integers less than n as input.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 7 bytes

êæIŒ€{K

Only takes the string as input. Outputs [""] for truthy, and a list with additional items as falsey, which is allowed because of the flexible rule "output can assume whatever form is most convenient. ... Additionally, anything may be used as a symbol provided it is distinct from all the other symbols." (taken from @emanresuA's Vyxal answer).
If a truthy/falsey value was mandatory, a trailing g (length) could be added, because only 1 is truthy in 05AB1E.

Try it online or verify all test cases.

Explanation:

ê        # Sorted uniquify the digits in the (implicit) input
 æ       # Pop and push its powerset list
  I      # Push the input
   Π    # Pop and push its substrings
    €{   # Sort each substring
      K  # Remove those from the powerset-list
         # (after which the result is output implicitly)
\$\endgroup\$
2
  • \$\begingroup\$ This would be 7 bytes by dropping teh g and using the same 'list of empty list' output as emanresu A's Vyxal answer (exploiting the rule "output can assume whatever form is most convenient")... \$\endgroup\$ Feb 8 at 9:14
  • \$\begingroup\$ @DominicvanEssen Thanks. \$\endgroup\$ Feb 8 at 11:42

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.