Ruby Get Permutations of All Lengths from a String in Order

Ruby get permutations of all lengths from a string in order

Array#repeated_permutation can do the heavy lifting for you here:

$arr = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-"
def scan
  characters = $arr.chars

  (1..6).each do |length|
    characters.repeated_permutation(length) do |sequence|
      t = sequence.join
      puts t
    end
  end
end

Or as a more reusable enumerator:

CHARACTERS = [*"A".."Z", *"a".."z", *"0".."9", "_", "-"]
def each_permuted_string(max_length = 6, &block)
  sequences = (1..max_length).map { |n| CHARACTERS.repeated_permutation(n) }

  if block_given?
    sequences.each { |seq| seq.lazy.map(&:join).each(&block) }
  else
    enum_for(__method__, max_length) { sequences.map(&:size).inject(:+) }
  end
end

each_permuted_string do |t|
  puts t
end

It's going to take a very long time, though -- there are each_permuted_string.size => 69810262080 values. This sounds like it could be an XY Problem, and you might get a better solution by asking a question about the higher-level problem you're solving.

Generate all possible permutations of characters with a given maximum length

What about ?

class Array
  def all_possibilities(range)
    return permutation(range).to_a if range < size

    (size..range).flat_map do |i|
      permutation(range - i).flat_map do |e|
        (self + e).permutation.to_a
      end
    end
  end
end

This returns an array of arrays of strings.

%w(a c).all_possibilities(3)
# => [["a", "c", "a"], ["a", "a", "c"], ["c", "a", "a"],
#     ["c", "a", "a"], ["a", "a", "c"], ["a", "c", "a"],
#     ["a", "c", "c"], ["a", "c", "c"], ["c", "a", "c"],
#     ["c", "c", "a"], ["c", "a", "c"], ["c", "c", "a"],
#     ["a", "c"], ["c", "a"]] 

To print it, you could just do result.map(&:join).join(', ').

ps: there is duplicates you could just avoid using uniq. It happens because you can have twice the same letter in an array like %w(a c a).

Algorithm to find all combinations of a string, maintain order, not fixed length

Here are two ways it could be done without making use of Array#combination. I've also included code for the case when combination is permitted (#3)¹.

1. Map each of the numbers between 1 and 2**n-1 (n being the length of the string) to a unique combination of characters from the string

def string_combinations(str)
  arr = str.chars
  (1..2**str.length-1).map do |n|
    pos = n.bit_length.times.map.with_object([]) { |i,a| a << i if n[i] == 1 }
    arr.values_at(*pos).join
  end.sort
end

string_combinations("wxyz")
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

Discrete probability theory provides us with the equation

sum(i = 1 to n) ( |i| C(n,i) ) == 2^n - 1

where C(n,i) is "the number of combinations of n things taken i at a time".

If the given string is "wxyz", n = "wxyz".length #=> 4, so there are 2**4 - 1 #=> 15 combinations of one or more characters from this string. Now consider any of the numbers between 1 and 16, say 11, which is 0b1011 in binary. Converting this to an array of binary digits, we obtain:

bin_arr = [1,0,1,1]

We now pluck out each character of wxyz for which the corresponding index position in bin_arr equals 1, namely

["w", "y", "z"]

and then join those elements to form a string:

["w", "y", "z"].join #=> "wyz"

Since each number 1 to 15 corresponds to a distinct combination of one or more characters from this string, , we can obtain all such combinations by repeating the above calculation for each the numbers between 1 and 15.

No matter which method you use, the resulting array will contain 2**n - 1 elements, so you are looking at O(2**str.length).

2. Use recursion

def string_combinations(str)
  (combos(str) - [""]).sort
end

def combos(str)
  return [str, ""] if str.length==1
  forward = combos str[1..-1]
  [*forward, *[str[0]].product(forward).map(&:join)]
end

string_combinations("wxyz")
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

Notice that

combos("wxyz")
  #=> ["z", "", "yz", "y", "xz", "x", "xyz", "xy",
  #    "wz", "w", "wyz", "wy", "wxz", "wx", "wxyz", "wxy"] 

includes an empty string, which must be removed, and the array needs sorting. Hence the need to separate out the recursive method combos.

3. Use Array#combination

Here we invoke arr.combination(n) for all values of n between 1 and arr.size and return a (flattened) array comprised of all n return values.

def string_combinations(str)
  a = str.chars
  (1..str.size).flat_map { |n| a.combination(n).map(&:join) }.sort
end

string_combinations "wxyz"
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

^{_{1 Since I wrote it before realizing that's not what the OP wanted. ¯\_(ツ)_/¯}}

Generate all permutations of the digits of a given number?

This is "cheating", because it uses intermediate strings which you didn't want to do, but it works:

9431.to_s.chars.to_a.permutation.map(&:join).map(&:to_i).uniq
=> [9431, 9413, 9341, 9314, 9143, 9134, 4931, 4913, 4391, 4319, 4193, 
    4139, 3941, 3914, 3491, 3419, 3194, 3149, 1943, 1934, 1493, 1439, 
    1394, 1349]

Ruby permutations

How about going the other way? Checking every word to make sure it only uses the allowed letters?
I tried this with the 3000 most common words and it worked plenty fast.

words = [..]
letters = [ "m", "o", "r" ]
words.each do |word|
  all_letters_valid = true
  word.chars.each do |char|
    unless letters.include?(char)
      all_letters_valid = false
      break
    end
  end
  if all_letters_valid
    puts word
  end
end

If letters can repeat there isn't a finite number of permutations so that approach doesn't make sense.

Assumption: English ascii characters only

All possible permutations of a given String?

%w[a b c].permutation.map &:join

---

Related Topics