All Possible Combinations of Selected Character Substitution in a String in Ruby

All possible combinations of selected character substitution in a string in ruby

string = "this is a test"
subs = ['a'=>'@','i'=>'!','s'=>'$']

subs = subs.first.map(&:to_a)
1.upto(subs.length).each do |n|
  subs.combination(n).each do |a|
    p a.each_with_object(string.dup){|pair, s| s.gsub!(*pair)}
  end
end

All possible combinations of selected character substitution in a string in ruby - Improved

Rather than your subs, the following one, which includes the information that replacement can vacuously apply, would be easier to handle:

subs = {"a" => ["a", "@"], "i" => ["i", "!"], "s" => ["s", "$", "&"]}

Using this, you should have sticked to my answer. The following is just a minor modification to my answer to your previous question:

string = "this is a test"

a = subs.values
a = a.first.product(*a.drop(1))

a.each do |a|
  p [subs.keys, a].transpose.each_with_object(string.dup){|pair, s| s.gsub!(*pair)}
end

which gives:

"this is a test"
"thi$ i$ a te$t"
"thi& i& a te&t"
"th!s !s a test"
"th!$ !$ a te$t"
"th!& !& a te&t"
"this is @ test"
"thi$ i$ @ te$t"
"thi& i& @ te&t"
"th!s !s @ test"
"th!$ !$ @ te$t"
"th!& !& @ te&t"

All possible permutations or combinations of a selected character substitution's in a string in ruby w/ permutations

Is this what you wanted?

string = "this is a test"
p = ?a, ?i, ?s
q = ?@, ?!, [ ?$, ?& ]

replacements = Hash.new { |h, e| Array e }.tap do |h|
  p.zip( q ).each { |p, q| h[p] = p, *Array( q ) }
end
#=> {"a"=>["a", "@"], "i"=>["i", "!"], "s"=>["s", "$", "&"]}

puts string.split( '' ).map( &replacements.method( :[] ) ).reduce( &:product ).map { |e|
  e.flatten.join
}

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 possible consecutive word combinations of a string

This solution avoids unnecessary joins :

word     = "hello"
size     = word.size
min_size = 3

(min_size..size).flat_map { |l| (0..size - l).map { |i| word[i, l] } }
#=> ["hel", "ell", "llo", "hell", "ello", "hello"]

If you don't need an Array but just need to iterate over every possible substring, this solution will use less memory :

(min_size..size).each do |l|
  (0..size - l).each do |i|
    # do something with word[i, l]
  end
end

Show all substring replacement options in Ruby

I'd do as below :

my_string = "yellow dogs are cooler than brown cats"
substitutions = {"yellow" => "black", "brown" => "grey"}

keys = substitutions.keys
arry_of_comb = 0.upto(substitutions.size).flat_map do |num|
  keys.combination(num).map do |ary| 
    my_string.gsub(/\b#{Regexp.union(ary)}\b/,substitutions) 
  end
end
arry_of_comb
# => ["yellow dogs are cooler than brown cats",
#     "black dogs are cooler than brown cats",
#     "yellow dogs are cooler than grey cats",
#     "black dogs are cooler than grey cats"]

Ruby string substitution with multiple options

def gen_products(swap, str)
  swap_all = Hash.new { |_,k| [k] }.merge(swap) 
  arr = swap_all.values_at(*str.chars)
  arr.shift.product(*arr).map(&:join)
end

See Hash::new (with a block), Hash#values_at and Array#product. If h = Hash.new { |_,k| [k] } and h does not have a key k, h[k] returns [k].

swap = { 'a'=>['$', '%', '^'], 'b'=>['3'], 'c'=>['4', '@'] }

gen_products(swap, "abc")
  #=> ["$34", "$3@", "%34", "%3@", "^34", "^3@"]

Here

swap_all = Hash.new { |_,k| [k] }.merge(swap) 
  #=> {"a"=>["$", "%", "^"], "b"=>["3"], "c"=>["4", "@"]}
vals = swap_all.values_at(*str.chars)
  #=> [["$", "%", "^"], ["3"], ["4", "@"]]

Another example:

gen_products(swap, "bca")
  #=> ["34$", "34%", "34^", "3@$", "3@%", "3@^"]

and one more:

gen_products(swap, "axbycx")
  #=> ["$x3y4x", "$x3y@x", "%x3y4x", "%x3y@x", "^x3y4x", "^x3y@x"]

Here

swap_all = Hash.new { |_,k| [k] }.merge(swap)
  #=> {"a"=>["$", "%", "^"], "b"=>["3"], "c"=>["4", "@"]}
vals = swap_all.values_at(*str.chars)
  #=> [["$", "%", "^"], ["x"], ["3"], ["y"], ["4", "@"], ["x"]]

ruby - How can I generate an array of every combination of letters and numbers of a given length?

alphanum = [*?a..?z, *?0..?9]
length.times.flat_map { |l|
  alphanum.repeated_permutation(l + 1).map(&:join)
}

Note that length > 3 will give you a lot of results.

EDIT: As meagar says, this is very memory-intensive. An Enumerator-based answer (not as pretty, but won't kill your memory):

e = Enumerator.new do |y|
  length.times do |l|
    alphanum.repeated_permutation(l + 1).each do |p|
      y << p.join
    end
  end
end

Ruby - replace characters in a string with a symbol

What about gsub(/\S/, '*')

It will find all non-whitespace characters and replace every one of them with *. \S is a regex character class matching non-whitespace chars (thanks @jdno).

E.g.

 pry> "as12 43-".gsub(/\S/, '*')
 => "**** ***"

So in your case:

def change_word(word)
   word.gsub(/\S/, '*')
end 

You may also extract the regex outside of the method to optimize it a bit:

CHANGE_WORD_PATTERN = /\S/
def change_word(word)
   word.gsub(CHANGE_WORD_PATTERN, '*')
end 

---

Related Topics