20
\$\begingroup\$

Super permutations

Input: A string
The program should loop through all lengths of the input (decrementing one each time), generate all combinations with replacement of the string, then make permutations out of the generated combinations, and display all of the strings. They can be separated with anything (doesn't need to be a comma)

Example for the string 'abc':

a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc
aaa, aab, aac, aba, abb, abc, aca, acb, acc
baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc
caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc

The values don't necessarily have to be sorted.
Avoid any standard loop holes.

\$\endgroup\$
  • 6
    \$\begingroup\$ Can we also include the empty string as a length zero permutation? \$\endgroup\$ – Jo King Jan 25 at 13:02
  • 7
    \$\begingroup\$ Will the string contain duplicates? If so, do you need the output to be deduplicated? \$\endgroup\$ – Neil Jan 25 at 16:31
  • 1
    \$\begingroup\$ I tagged this code golf, because all the answers are assuming it is. \$\endgroup\$ – xnor Jan 25 at 18:57
  • 9
    \$\begingroup\$ I'm finding the talk of permutations and combinations confusing here. The way I'd phrase the task is: output all strings made of characters in the input, whose length ranges from 1 to the length of the input. Related: Output all strings. \$\endgroup\$ – xnor Jan 25 at 18:59
  • 1
    \$\begingroup\$ Can we take a length argument? \$\endgroup\$ – S.S. Anne Jan 26 at 14:09

19 Answers 19

13
\$\begingroup\$

Scratch 3.0, 65 blocks / 637 632 bytes

Part 1

Part 2

Part 3

Part 4

Look at y'all, having fun with your fancy shmancy permutation functions/map tools. Well, not I! No, not I! When using Scratch, one has to do things themselves! You won't find any built-ins around these parts! I'm just glad there still ain't any gotos ;)

But more seriously, the image is split into 4 parts because it's just soooo long Press space to clear the lists before each run

And finally,

Try it online Scratch!

As SB Syntax:

when gf clicked
set[c v]to(0
ask()and wait
set[L v]to(length of(answer
add(1)to[b v
repeat((L)-(1
add(0)to[b v
end
repeat until<(c)=(1
set[s v]to(0
set[l v]to(1
repeat(length of[b v
change[s v]by(item(l)of[b v
change[l v]by(1
end
if<(s)=((L)*(L))>then
set[c v]to(1
end
set[r v]to(
set[l v]to(1
repeat(length of[b v
set[r v]to(join(r)(letter(item(i)of[b v])of(answer
change[i v]by(1
end
add(r)to[o v
replace item(1)of[b v]with((item(1)of[b v])+(1
set[j v]to(1
repeat(length of[b v
if<(item(j)of[b v])>(length of(answer))>then
replace item(j)of[b v]with(1
replace item((j)+(1))of[b v]with((item((j)+(1))of[b v])+(1
end
change[j v]by(1

-5 bytes due to not being a silly billy and removing extranous spaces

\$\endgroup\$
8
\$\begingroup\$

05AB1E, 4 3 bytes

-1 byte thanks to a'_'

ā€ã

Try it online!

\$\endgroup\$
  • 6
    \$\begingroup\$ I don't know 05AB1E. I just randomly pasted a character inside the program. And it WORKS!? \$\endgroup\$ – user85052 Jan 25 at 13:59
  • \$\begingroup\$ @a'_' you what? That sounds insanely unlikely lol \$\endgroup\$ – Cruncher Jan 28 at 14:21
  • \$\begingroup\$ @Cruncher I am serious. I thought turning the gL into ã (i.e. a double-cartesian power) would work. It turns out that I copied the wrong character (ā indeed looks very similar to ã) \$\endgroup\$ – user85052 Jan 28 at 14:24
  • \$\begingroup\$ (And then I feel that pretending that I don't know 05AB1E and saying randomly will make viewers laugh harder.) \$\endgroup\$ – user85052 Jan 28 at 14:33
7
\$\begingroup\$

Jelly, 2 bytes

ṗJ

A monadic Link which accepts a list of characters and returns a list of lists of lists of characters.

Try it online! (footer formats as a grid)

How?

ṗJ - list, S
 J - range of length of S
ṗ  - Cartesian power (vectorises)

If we must output a flat list of "strings" (lists of characters) we can add (tighten) for the cost of a byte.

\$\endgroup\$
6
\$\begingroup\$

Haskell, 34 bytes

f s=init$mapM(\_->s)=<<scanr(:)[]s

Try it online!

Here's how it works, using input s="abc":

                       scanr(:)[]s

Produces the suffixes of s, ["abc","bc","c",""], by prepending each character in turn to the front and tracking the intermediate results.

         mapM(\_->s)

Uses the list monad to map each element to s, that is, 'xy'-> ["abc","abc"], and take multiply them as a Cartesian product, here giving ["aa","ab","ac","ba","bb","bc","ca","cb","cc"].

         mapM(\_->s)=<<scanr(:)[]s

Uses =<< as concatMap to take the function above that uses mapM and apply it to each of the suffixes, thereby producing the Cartesian products of copies of s numbering from 0 to its length, in a single list.

    init$

Removes the empty string, produces from the suffix of length 0.

f s=

Declares the function.

\$\endgroup\$
  • \$\begingroup\$ What is going on here? \$\endgroup\$ – RGS Jan 25 at 21:57
  • \$\begingroup\$ Thanks for the explanation! \$\endgroup\$ – RGS Jan 27 at 18:36
5
\$\begingroup\$

05AB1E, 6 bytes

gENIã)

Try it online!

Explanation

gENIã)
 E     # foreach in...
g      # the input
    ã  # find the cartesian product of...
   I   # the input...
  N    # repeat N
     ) # wrap the final stack to an array
       # implicit output of the top element
\$\endgroup\$
  • 14
    \$\begingroup\$ That looks like genial, which in my (natural) language means brilliant. +1 for that \$\endgroup\$ – RGS Jan 25 at 12:18
3
\$\begingroup\$

J, 16 bytes

a:-.~[:,#\{@#"{<

Try it online!

  • a:-.~ Remove empty boxes from...
  • [:, The flatten of...
  • {@#"{ The Catalog (cross prod) of {@...
  • #\{@#"{<
    • < The boxed input...
    • #"{ Copied this many times...
    • #\ 1, 2, ... N, where N is the input length. That is, we copy the input once, then twice, ... then N times, taking the Catalog of each of those.
\$\endgroup\$
3
\$\begingroup\$

PowerShell, 42 bytes

($a=$args)|%{($p=$p|%{$t=$_;$a|%{$t+$_}})}

Try it online.

Expects input via splatting.

\$\endgroup\$
  • \$\begingroup\$ via $null. it's smart! \$\endgroup\$ – mazzy Jan 27 at 8:20
3
\$\begingroup\$

PHP, 176 174 173 171 170 166 bytes

$c=$t=count($u=array_values(array_unique(str_split($argn))));for($s=1;$i<$t**$t;){$i-$c?:[$s++,$c*=$t,$i=0];for($k=$i++,$j=0;$j<$s;$j++,$k/=$t)echo$u[$k%$t];echo',';}

Try it online!

-4 bytes thanks to @Ismael Miguel.

Method: simply count in base N, where N is the number of unique characters in the input string.

\$\endgroup\$
  • \$\begingroup\$ You can save 2 bytes by moving $k/=$t; into the for($j=0;$j<$s;$j++), and remove the {...}, like this: for($j=0;$j<$s;$j++,$k/=$t)echo$u[$k%$t]; \$\endgroup\$ – Ismael Miguel Jan 27 at 9:30
  • \$\begingroup\$ Didn't think PHP supported the comma operator. But yes, in for loops! \$\endgroup\$ – Guillermo Phillips Jan 27 at 9:51
  • \$\begingroup\$ Oh, it works. And here's something else: you can replace your if($i==$c){$s++;$c*=$t;$k=$i=0;} with $i==$c?[$s++,$c*=$t,$k=$i=0]:0;. This will save 1 byte, and work the same. This uses a ternary operator and an array, where the array will be "executed" if the condition is true. However, you need to have a value for the false condition (the 0). What saves the byte is really the array, because you remove the ; after the 3rd assignment, when changing the syntax. \$\endgroup\$ – Ismael Miguel Jan 27 at 10:04
  • 1
    \$\begingroup\$ Very clever, I shall use it in future. I switched the condition however, for one extra byte: $i!=$c?:[$s++,$c*=$t,$k=$i=0]; \$\endgroup\$ – Guillermo Phillips Jan 27 at 10:18
  • \$\begingroup\$ That is actually really clever. I didn't though about it. But hey, 5 bytes shaved from the total is pretty good. \$\endgroup\$ – Ismael Miguel Jan 27 at 10:24
2
\$\begingroup\$

Python 3, 95 bytes

import itertools as i;lambda s:[''.join(p)for l in range(len(s))for p in i.product(s,repeat=l)]

Try it online

\$\endgroup\$
  • 1
    \$\begingroup\$ Using l here made me confuse it with 1 for a second back in the repeat= part... +1! \$\endgroup\$ – ojdo Jan 27 at 11:51
  • \$\begingroup\$ @ojdo maybe not the best choice on my part :P \$\endgroup\$ – RGS Jan 27 at 12:37
  • \$\begingroup\$ Note: you can format your TIO code like this for anonymous lambdas with imports \$\endgroup\$ – Jo King Jan 29 at 23:26
  • \$\begingroup\$ @JoKing That does look better! Thanks! \$\endgroup\$ – RGS Jan 29 at 23:34
2
\$\begingroup\$

Python 2, 69 68 bytes

f=lambda s,A={''}:s in A and A or f(s,A|{a+c for a in A for c in s})

Try it online!

Outputs a set; includes the empty string.

Python 2, 71 bytes

f=lambda s,A=[]:s in A and A or f(s,set(s)|{a+c for a in A for c in s})

Try it online!

If empty string is not allowed...

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

JavaScript (ES7), 90 bytes

Returns a Set.

s=>new Set([...Array(n=(L=-~s.length)**~-L)].map(_=>(g=n=>n?[s[n%L-1]]+g(n/L|0):'')(n--)))

Try it online!

Commented

s => new Set(            // build a set from
  [...Array(             //   an array of
    n =                  //   n entries, with:
      (L = -~s.length)   //     n = L ** (L - 1)
      ** ~-L             //     where L is the length of s + 1
  )]                     //   
  .map(_ =>              //   for each entry:
    ( g = n =>           //     g is a recursive function taking n
        n ?              //       if n is not equal to 0:
          [s[n % L - 1]] //         output s[(n mod L) - 1]
                         //         or an empty string if it's undefined
          + g(n / L | 0) //         recursive call with floor(n / L)
        :                //       else:
          ''             //         stop recursion
    )(n--)               //     initial call to g; decrement n afterwards
  )                      //   end of map()
)                        // end of Set()
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 17 bytes

FEθXLθ⊕κEι✂⍘⁺ικθ¹

Try it online! Link is to verbose version of code. Explanation:

FEθXLθ⊕κ

Loop over the substring lengths and raise the length to each power in turn.

Eι✂⍘⁺ικθ¹

Loop from each power to double its value and perform base conversion using the input string as the alphabet, then slice off the first character.

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

Husk, 4 bytes

Total Husk novice, there may be better ways to golf this.

Mπŀ¹

Try it online!

Explanation

  ŀ¹ Find the range [1, ..., len(input)]
Mπ   Map with cartesian power of input
\$\endgroup\$
2
\$\begingroup\$

Burlesque,  5  4 bytes

sacb

Try it online!

-1 thanks to DeathIncarnate!

sa    # Duplicate the input and get it's length
  cb  # Get all combinations of the input characters up to the length of the input
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 32 bytes

{flat [\X~] '',|[xx] .comb xx 2}

Try it online!

Anonymous code block that takes a string and returns a list of string including the length zero permutation.

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

Pyth, 5 bytes

^LQSl

Try it here!

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

Ruby, 60 bytes

->s{a,*z=s.chars,'';z.product(*a.map{a+z}).map(&:join)-z|[]}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

R, 112 bytes

function(S,s=sapply)cat(unlist(s(1:nchar(S),function(X)do.call('paste0',expand.grid(s(rep(S,X),strsplit,''))))))

Try it online!

Things that make you go Argh, strings in R.

Expands out to the following

cat(                                           # output the results
  unlist(                                      # collapse the list
    sapply(1:nchar(S),                         # for 1 to character length of S
      function(X)do.call('paste0',             # for each row from the grid paste characters together
         expand.grid(                          # create permutations 
           sapply(rep(S,X),strsplit,''))))))   # replicate the string X times and split.

So we produce a lists of [['a','b','c']], [['a','b','c'],['a','b','c']], [['a','b','c'],['a','b','c'],['a','b','c']]. These are feed into expand.grid to produce the permutations.

Each row of the grid is pasted together with no gaps in the do.call.

As it is still in a list we apply unlist so that cat will be able to output it.

\$\endgroup\$
  • \$\begingroup\$ depending on whether you are allowed to output the list directly (it's asked in comments but as yet unanswered) you could replace cat(unlist(...)) with print(...) (maybe show(...) will work also — haven't tried) \$\endgroup\$ – JDL Jan 28 at 14:14
  • \$\begingroup\$ I could probably just get rid of them completely. There could also be an argument put forward to remove the do.call \$\endgroup\$ – MickyT Jan 28 at 18:08
0
\$\begingroup\$

Perl 5 -lF, 48 bytes

$"=',';map$k{$_}++||say,glob"{@F}"."{@F,''}"x$#F

Try it online!

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