22
\$\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\$
12
  • \$\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\$ Jul 24, 2020 at 7:52
  • \$\begingroup\$ You are correct, I will edit this quickly before there are too many responses @KevinCruijssen \$\endgroup\$
    – golf69
    Jul 24, 2020 at 7:54
  • \$\begingroup\$ I would make the input \$n\$ optional, since the Japt and APL answer are already using the input \$n\$. \$\endgroup\$ Jul 24, 2020 at 7:58
  • \$\begingroup\$ Good idea @KevinCruijssen \$\endgroup\$
    – golf69
    Jul 24, 2020 at 8:00
  • 1
    \$\begingroup\$ Imaginary bonus for answers that takes polynomial time in the input... \$\endgroup\$
    – DELETE_ME
    Jul 24, 2020 at 16:37

20 Answers 20

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)
\$\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?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You should be aware: n is now optional (though your answer is still valid) \$\endgroup\$
    – golf69
    Jul 24, 2020 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, 2020 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!

\$\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()
\$\endgroup\$
3
  • \$\begingroup\$ Possible 80 bytes? Passes the test cases, at least. \$\endgroup\$
    – Shaggy
    Jul 24, 2020 at 18:23
  • \$\begingroup\$ @Shaggy That would not generate all permutations and report many false-positive such as "1232131". \$\endgroup\$
    – Arnauld
    Jul 24, 2020 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, 2020 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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You should be aware: n is now optional (though your answer is still valid) \$\endgroup\$
    – golf69
    Jul 24, 2020 at 8:01
5
\$\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)?
)
\$\endgroup\$
3
  • 3
    \$\begingroup\$ You are answering a lot with Io recently. Care to create another Increment room? \$\endgroup\$ Jul 24, 2020 at 9:15
  • 1
    \$\begingroup\$ @HighlyRadioactive Io is a simple, concise, and fun langauge. You should really try it! (The Increment is created btw.) \$\endgroup\$
    – user92069
    Jul 24, 2020 at 10:11
  • 1
    \$\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\$ Jul 24, 2020 at 10:43
4
\$\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
\$\endgroup\$
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!\$.

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

\$\endgroup\$
1
  • \$\begingroup\$ If an interpreter exists with that library installed then your 66 byte solution should be valid. \$\endgroup\$
    – Shaggy
    Jul 26, 2020 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?
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

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

Try it online!

@att saved 31 bytes

\$\endgroup\$
1
  • \$\begingroup\$ 44 bytes \$\endgroup\$
    – att
    Jul 25, 2020 at 1:52
2
\$\begingroup\$

Haskell, 57 bytes

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

Try it online!

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

Husk, 5 bytes

Λ€¹Pu

Try it online!

Same as the Jelly answer.

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

Scala -deprecation -encoding=UTF-8 -feature -unchecked -language:postfixOps -language:implicitConversions -language:higherKinds -language:existentials -language:postfixOps -Xfuture -Yno-adapted-args -Ywarn-dead-code -Ywarn-numeric-widen -Ywarn-value-discard -Ywarn-unused, 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!

\$\endgroup\$
1
\$\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.

\$\endgroup\$
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
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 9 bytes

UṖƛ∑⁰$c;A

Try it Online!

A mess.

\$\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
\$\endgroup\$
0
\$\begingroup\$

Ruby -nl, 44 bytes

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

Try it online!

\$\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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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