21
\$\begingroup\$

A superpermutation on n symbols is a string which contains every permutation of n symbols in its body. For instance, 123121321 is a superpermutation on three symbols because it contains 123, 132, 213, 231, 312 and 321 as substrings.

The Challenge

Given a string composed of n unique symbols (and, optionally, n), output whether it is a superpermutation 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: 11
Out: True

In: 123121321
Out: True

In: 12312131
Out: False

See also: this question about generating superpermutations

\$\endgroup\$
  • \$\begingroup\$ Is \$n\$ always equal to the unique amount of digits? If yes, do we even need input \$n\$? If no, could you add a test case for this? \$\endgroup\$ – Kevin Cruijssen Jul 24 at 7:52
  • \$\begingroup\$ You are correct, I will edit this quickly before there are too many responses @KevinCruijssen \$\endgroup\$ – golf69 Jul 24 at 7:54
  • \$\begingroup\$ I would make the input \$n\$ optional, since the Japt and APL answer are already using the input \$n\$. \$\endgroup\$ – Kevin Cruijssen Jul 24 at 7:58
  • \$\begingroup\$ Good idea @KevinCruijssen \$\endgroup\$ – golf69 Jul 24 at 8:00
  • \$\begingroup\$ This is probably asking for too much, but may we take the list/set of unique symbols as input? \$\endgroup\$ – cole Jul 24 at 8:44

19 Answers 19

9
\$\begingroup\$

05AB1E, 4 bytes

ÙœåP

Only takes input \$J\$ (I don't need \$n\$ with this approach).

Try it online or verify all test cases.

Explanation:

Ù     # Uniquify the digits of (implicit) input-integer
 œ    # Get all permutations of this uniquified integer
  å   # Check for each if it's a substring of the (implicit) input-integer
   P  # And check if this is truthy for all of them
      # (after which the result is output implicitly)
| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

APL (Dyalog Unicode), 20 bytes

{(!⍺)=+/⍺=⍴∘∪¨∪⍺,/⍵}

Try it online!

Takes n on the left and J on the right

How?

⍺,/⍵   ⍝ Overlapping sublists of length n in J
∪      ⍝ Unique sublists
⍴∘∪¨   ⍝ Length of the unique elements of each unique sublist
+/⍺=   ⍝ How many are equal to n?
(!⍺)=  ⍝ Is this equal to the number of permutations of n symbols?
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You should be aware: n is now optional (though your answer is still valid) \$\endgroup\$ – golf69 Jul 24 at 8:01
  • \$\begingroup\$ You can use ∪/ instead of ∪¨,/, giving 18 bytes dfn and 16 bytes tacit (tacit is 18.0 only): Try it online! \$\endgroup\$ – Bubbler Jul 26 at 23:23
7
\$\begingroup\$

Python 3, 79 bytes

lambda s:all(''.join(p)in s for p in permutations({*s}))
from itertools import*

Try it online!


Python 2, 81 bytes

lambda s:all(''.join(p)in s for p in permutations(set(s)))
from itertools import*

Try it online!

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

JavaScript (ES6),  83 82  81 bytes

Returns 0 if the input string is a superpermutation, or 1 if it's not.

f=(s,a=[...new Set(s)],p)=>!s.match(p)|a.some((c,n)=>f(s,a.filter(_=>n--),[p]+c))

Try it online!

How?

If all permutations of the \$N\$ symbols are present in the input string \$s\$, so are all prefixes of said permutations. Therefore, it's safe to test that all \$p\$ are found in \$s\$ even when \$p\$ is an incomplete permutation whose size is less than \$N\$.

That's why we can use a function that recursively builds each permutation \$p\$ of the symbols and tests whether \$p\$ exists in \$s\$ at each iteration, even when \$p\$ is still incomplete.

Commented

f = (                     // f is a recursive function taking:
  s,                      //   s = input string
  a = [...new Set(s)],    //   a[] = list of unique characters in s
  p                       //   p = current permutation, initially undefined
) =>                      //
  !s.match(p) |           // force the result to 1 if p is not found in s
                          // NB: s.match(undefined) is truthy because it's equivalent
                          //     to looking for an empty string in s
  a.some((c, n) =>        // for each character c at position n in a[]:
    f(                    //   do a recursive call:
      s,                  //     pass s unchanged
      a.filter(_ => n--), //     remove the n-th character in a[] (0-indexed)
      [p] + c             //     coerce p to a string and append c to p
    )                     //   end of recursive call
  )                       // end of some()
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Possible 80 bytes? Passes the test cases, at least. \$\endgroup\$ – Shaggy Jul 24 at 18:23
  • \$\begingroup\$ @Shaggy That would not generate all permutations and report many false-positive such as "1232131". \$\endgroup\$ – Arnauld Jul 24 at 18:29
  • \$\begingroup\$ Thought it might have been too good to be true. Discovered far too many false positives meself while working on my own solution. We could do with a few more test cases covering more edge cases. \$\endgroup\$ – Shaggy Jul 24 at 20:55
6
\$\begingroup\$

Japt v2.0a0, 10 8 bytes

Saved 2 bytes with the clarification that the string can only contain the digits in [1,n].

â á e!øU

Try it

â á e!øU     :Implicit input of string U
â            :Deduplicate
  á          :Permutations
    e        :All
     !øU     :  Contained in U
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You should be aware: n is now optional (though your answer is still valid) \$\endgroup\$ – golf69 Jul 24 at 8:01
4
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

Union[##~Partition~1]~Count~{a__/;0!=a}<#2!&

Try it online!

Takes a list of characters and \$n\$ as input. Returns False if the string is a superpermutation, and True otherwise.

Verifies that the number of unique sequences of \$n\$ distinct characters is (un)equal to \$n!\$.

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

Io, 104 bytes

method(x,n,K :=Range 1 to(n)asList;x map(i,v,x slice(i,i+n))unique select(x,x sort==K)size==K reduce(*))

Try it online!

Explanation (Ungolfed)

method(x,n,                        // Take the string and the num of uniquified integers
    K := Range 1 to(n)asList       // K = [1..n]
    x map(i,v,x slice(i,i+n))      // All slices of x of length n
    unique                         // Uniquify these slices
    select(x,                      // Filter: (x : current item)
        x sort==K                  //     sort(x) == [1..n]?
    ) size                         // Number of items that satisfy this
    == K reduce(*)                 // == factorial(n)?
)
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ You are answering a lot with Io recently. Care to create another Increment room? \$\endgroup\$ – null Jul 24 at 9:15
  • \$\begingroup\$ @HighlyRadioactive Io is a simple, concise, and fun langauge. You should really try it! (The Increment is created btw.) \$\endgroup\$ – user92069 Jul 24 at 10:11
  • \$\begingroup\$ I don't have time to try it LOL. I'm busy with 1+ minimalization. I'll post more in the Increment room and you should really join it. \$\endgroup\$ – null Jul 24 at 10:43
3
\$\begingroup\$

Brachylog, 7 bytes

dpᶠ~sᵛ?

Same algorithm as @Kevin Cruijssen, so upvote that.

Try it online!

How it works

dpᶠ~sᵛ?
d       deduplicate input
 pᶠ     find all permutations
   ~sᵛ  all of them must be substrings of
      ? the input
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

R + gtools, 79 bytes

function(x,n)all(sapply(apply(permutations(n,n),1,paste0,collapse=""),grepl,x))

Try it online!

An example of some awfully-verbose names for R functions and mandatory arguments!

Generates all permutations of digits 1..n, pastes them together as strings, and checks that all are present in the input string.

An alternative 66 byte solution using the R "combinat" library would be: function(x,n,`[`=sapply)all(permn(n)[paste0,collapse=""][grepl,x]), but unfortunately this library isn't installed on TIO.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ If an interpreter exists with that library installed then your 66 byte solution should be valid. \$\endgroup\$ – Shaggy Jul 26 at 14:52
2
\$\begingroup\$

Jelly, 5 bytes

Œ!ẇ€Ạ

A dyadic Link accepting \$n\$ on the left and the candidate as a list of integers on the right which yields 1 (is) or 0 (is not) as appropriate.

Try it online!

How?

Œ!ẇ€Ạ - Link: n, L
Œ!    - all permutations of [1..n]
   €  - for each (permutation, p):
  ẇ   -   is (p) a sublist of (L)?
    Ạ - all?
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

Subsequences@#~SubsetQ~Permutations@Union@#&

Try it online!

@att saved 31 bytes

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 44 bytes \$\endgroup\$ – att Jul 25 at 1:52
1
\$\begingroup\$

Pyth, 10 bytes

.Am}dz.p{z

Try it online!


Explanation:

.Am}dz.p{z
        {z  Deduplicate, yielding the distinct digits
      .p    Permutate
  m         Map with d as variable
   }dz      Check if d is a substring of z
.A          Verify that all elements are truthy
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Haskell, 57 bytes

import Data.List
s p=all(`isInfixOf`p)$permutations$nub$p

Try it online!

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

Husk, 5 bytes

Λ€¹Pu

Try it online!

Same as the Jelly answer.

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

Charcoal, 35 bytes

Nθ⁼ΠEθ⊕ιLΦEη✂ηκ⁺κθ¹∧⁼κ⌕ηι⁼θLΦι⁼μ⌕ιλ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a superpermutation, nothing if not. Explanation:

Nθ

Input n as a number.

⁼ΠEθ⊕ι

n! must equal...

LΦEη✂ηκ⁺κθ¹

... the number of truncated suffixes of the string...

∧⁼κ⌕ηι

... that have not already been seen earlier in the string, and...

⁼θLΦι⁼μ⌕ιλ

... contain n distinct characters.

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

Java 10, 291 287 233 229 bytes

n->{var t="";for(var d:n.split(t))t+=t.contains(d)?"":d;return p(n,"",t);}boolean p(String n,String p,String s){int l=s.length(),i=0;var r=n.contains(p);for(;i<l;)r&=p(n,p+s.charAt(i),s.substring(0,i)+s.substring(++i));return r;}

-4 bytes by taking inspiration from what @Arnauld mentioned in his JavaScript answer:

If all permutations of the \$N\$ symbols are present in the input string \$s\$, so are all prefixes of said permutations. Therefore, it's safe to test that all \$p\$ are found in \$s\$ even when \$p\$ is an incomplete permutation whose size is less than \$N\$.

That's why we can use a recursive function that recursively builds each permutation \$p\$ of the symbols and tests whether \$p\$ exists in \$s\$ at each iteration, even when \$p\$ is still incomplete.

Takes the integer-input as String.

Try it online.

Explanation:

n->{                    // Method with String as parameter and boolean return-type
  var t="";             //  Temp String, starting empty
  for(var d:n.split(t)) //  Loop over the digits of the input:
    t+=                 //   Append to String `t`:
       t.contains(d)?   //    If `t` contains this digit already:
        ""              //     Append nothing
       :                //    Else (it doesn't contain this digit yet):
        d;              //     Append this digit
  return p(n,"",t);}    //  Call the separated recursive method to check if each
                        //  permutation of `t` is a substring of `n` and return it as

// Separated recursive method to get all permutations of String `t`, and check for each
// if it's a substring of String `n`
boolean p(String n,String p,String s){
  int l=s.length(),    //  Get the length of the input-String `s`
      i=0;             //  Set the index `i` to 0
  var r=               //  Result-boolean, starting at:
        n.contains(p); //   Check that String `n` contains part `p` as substring instead
                       //   (this doesn't necessary have to be the full permutation,
                       //    but it doesn't matter if the part is smaller)
  for(;i<l;)           //  Loop `i` in the range [0, length):
    r&=                //   Add the following to the boolean-return (bitwise-AND style):
      p(               //    Do a recursive call with:
        n,p            //     The current part,
          +s.charAt(i),//     appended with the `i`'th character as new part
          s.substring(0,i)+s.substring(++i));
                       //     And the String minus this `i`'th character as new String
                       //     (and increment `i` for the next iteration in the process)
  return r;}           //  And return the resulting boolean
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Scala, 44 bytes

s=>s.distinct.permutations forall s.contains

Pretty straightforward. Finds all the distinct symbols, generates all their permutations, and then checks if each permutation is in the input string.

Try it online

Scala, 56 54 bytes

(s,>)=>(1 to>).mkString.permutations forall s.contains

As you can tell, the superpermutation string is | s(lot less readable now) and n is >. It basically just generates every permutation in the range 1 to n and checks if each of those are in the input string.

Try it online!

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

Ruby -nl, 44 bytes

p$_.chars.uniq.permutation.all?{|x|$_[x*'']}

Try it online!

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

T-SQL, 186 bytes

Returns 1 for true, 0 for false.

This struggles with more than 6 unique characters

WITH B as(SELECT distinct substring(@,number,1)a FROM spt_values),C
as(SELECT a y FROM b UNION ALL SELECT y+a FROM B,C
WHERE y like'%'+a+'%')SELECT 1/sum(1)FROM C WHERE replace(@,y,'')=@

Try it online ungolfed

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