Finding all permutations of array elements as concatenated strings

A fun problem! I wanted to implement using generators. This allows you to work with the permutations one-by-one as they are generated, rather than having to compute all permutations before the entire answer is provided –

const input =
  ["🔴","🟢","🔵","🟡"]

for (const p of permutations(input))
  console.log(p.join(""))

🔴🟢🔵🟡
🟢🔴🔵🟡
🟢🔵🔴🟡
🟢🔵🟡🔴
🔴🔵🟢🟡
🔵🔴🟢🟡
🔵🟢🔴🟡
🔵🟢🟡🔴
🔴🔵🟡🟢
🔵🔴🟡🟢
🔵🟡🔴🟢
🔵🟡🟢🔴
🔴🟢🟡🔵
🟢🔴🟡🔵
🟢🟡🔴🔵
🟢🟡🔵🔴
🔴🟡🟢🔵
🟡🔴🟢🔵
🟡🟢🔴🔵
🟡🟢🔵🔴
🔴🟡🔵🟢
🟡🔴🔵🟢
🟡🔵🔴🟢
🟡🔵🟢🔴

This allows us to do cool things like, finding specific patterns –

// find all permutations where red is left of green
for (const p of permutations(input))
  if (p.indexOf("🔴") < p.indexOf("🟢"))
    console.log(p.join(""))

🟡🔵🔴🟢
🔵🟡🔴🟢
🔵🔴🟢🟡
🔵🔴🟡🟢
🟡🔴🟢🔵
🟡🔴🔵🟢
🔴🟢🟡🔵
🔴🟡🟢🔵
🔴🟡🔵🟢
🔴🟢🔵🟡
🔴🔵🟢🟡
🔴🔵🟡🟢

// find all permutations where blue and yellow are adjacent
for (const p of permutations(input))
  if (Math.abs(p.indexOf("🔵") - p.indexOf("🟡")) == 1)
    console.log(p.join(""))

🟢🟡🔵🔴
🟡🔵🟢🔴
🟡🔵🔴🟢
🟢🔵🟡🔴
🔵🟡🟢🔴
🔵🟡🔴🟢
🟢🔴🟡🔵
🔴🟢🟡🔵
🔴🟡🔵🟢
🟢🔴🔵🟡
🔴🟢🔵🟡
🔴🔵🟡🟢

And if we wanted to find the only the first permutation where such a condition is true, we can use return or break to stop the generator and no more permutations will be computed.

We just have to implement permutations –

function* permutations (t)
{ if (t.length < 2)
    yield t
  else
    for (const p of permutations(t.slice(1)))
      for (const r of rotations(p, t[0]))
        yield r
}

Which depends on rotations –

function* rotations (t, v)
{ if (t.length == 0)
    yield [v]
  else
    yield *chain
      ( [[v, ...t]]
      , map(rotations(t.slice(1), v), r => [t[0], ...r])
      )
}

Which depends on two generic functions for working with iterables, map and chain –

function* map (t, f)
{ for (const e of t)
    yield f(e)
}

function* chain (...ts)
{ for (const t of ts)
    for (const e of t)
      yield e
}

Expand the snippet to verify the results in your own browser

function* permutations (t)
{ if (t.length < 2)
    yield t
  else
    for (const p of permutations(t.slice(1)))
      for (const r of rotations(p, t[0]))
        yield r
}

function* rotations (t, v)
{ if (t.length == 0)
    yield [v]
  else
    yield *chain
      ( [[v, ...t]]
      , map(rotations(t.slice(1), v), r => [t[0], ...r])
      )
}

function* map (t, f)
{ for (const e of t)
    yield f(e)
}

function* chain (...ts)
{ for (const t of ts)
    for (const e of t)
      yield e
}

const input =
  ["🔴","🟢","🔵","🟡"]

console.log("\nred is left of green")
for (const p of permutations(input))
  if (p.indexOf("🔴") < p.indexOf("🟢"))
    console.log(p.join(""))

console.log("\nblue and yellow are adjacent")
for (const p of permutations(input))
  if (Math.abs(p.indexOf("🔵") - p.indexOf("🟡")) == 1)
    console.log(p.join(""))

I hope you enjoyed this post as much as I enjoyed writing it 😀

To compute combinations using a similar technique, see this related Q&A.