如何创建一个方法来检查 string1 是否可以重新排列为相等的 string2

Question

我已经尝试编写方法，但是当我的代码没有运行时，我不确定为什么。

str1 = "cored"
str2 = "coder"
def StringScramble(str1,str2)
  numCombos = str1.length.downto(1).inject(:*)
  arr = []
  until arr.length == numCombos
    shuffled = str1.split('').join
    unless arr.include?(shuffled) 
      arr << shuffled 
    end
  end
  if arr.include?(str1)
    return true
  else 
    return false
  end
end

Answer 1

更新：正如@eugen在评论中指出的那样，有一种更有效的方法：

str1.chars.sort == str2.chars.sort # => true

原答案：

str1.chars.permutation.include?(str2.chars) # => true

Answer 2

最有效的方法？

比较排序字符串当然是最简单的方法，但如果效率是最重要的，你能做得更好吗？上个月，@raph发表了一条评论，提出了一种对我来说听起来不错的方法。我打算根据标准测试对其进行基准测试，但从未解决过。我回答的目的是将建议的方法与标准方法进行比较。

挑战者

这个想法是为其中一个字符串中的字符创建一个计数哈希h，以便h['c']等于'c'在字符串中出现的次数。 然后，一个遍历第二个字符串的字符。假设'c'是这些角色之一。然后 false 如果 h.key?('c') => false 或 h['c'] == 0 则由方法返回（也可以写h['c'].to_i == 0，如nil.to_i => 0）;否则，将根据哈希检查第二个字符串的下一个字符。假设字符串的长度相等，则当且仅当在检查了第二个字符串的所有字符后仍未返回false时，它们才是彼此的字谜。为两个字符串中较短的字符串创建哈希可能会提供进一步的改进。 这是我的方法代码：

def hcompare(s1,s2)
  return false unless s1.size == s2.size
  # set `ss` to the shorter string, `sl` to the other.
  ss, sl = (s1.size < s2.size) ? [s1, s2] : [s2, s1]    
  # create hash `h` with letter counts for the shorter string:
  h = ss.chars.each_with_object(Hash.new(0)) { |c,h| h[c] += 1}    
  #decrement counts in `h` for characters in `sl`
  sl.each_char { |c| return false if h[c].to_i == 0; h[c] -= 1 }    
  true
end

现任者

def scompare(s1,s2)
  s1.chars.sort == s2.chars.sort
end

助手

methods = [:scompare, :hcompare]
def compute(m,s1,s2)
  send(m,s1,s2)
end
def shuffle_chars(s)
  s.chars.shuffle.join
end

测试数据

reps = 20
ch = [*'b'..'z']

基准

require 'benchmark'
[50000, 100000, 500000].each do |n|
  t1 = Array.new(reps) { (Array.new(n) {ch.sample(1) }).join}
  test_strings = { true=>t1.zip(t1.map {|s| shuffle_chars(s)})}
  test_strings[false]  = t1.zip(t1.map {|t| shuffle_chars((t[1..-1] << 'a'))})
  puts "nString length #{n}, #{reps} repetitions"
  [true, false].each do |same|
    puts "nReturn #{same} "
    Benchmark.bm(10) do |bm|
      methods.each do |m|
        bm.report m.to_s do
          test_strings[same].each { |s1,s2| compute(m,s1,s2) }
        end
      end
    end  
  end
end

执行的比较

我比较了两种方法，scompare（使用sort）和hcompare（使用hash），对三种字符串长度执行基准测试：50，000，100，000和500，000个字符。对于每个字符串长度，我通过从[*('b'..'z')]中随机选择每个字符来创建两个字符串中的第一个。然后，我创建了两个字符串以与第一个字符串进行比较。一个只是对第一个字符串的字符进行洗牌，因此当比较这两个字符串时，方法将返回true。 在第二种情况下，我做了同样的事情，除了我用'a'替换了一个随机选择的字符，所以方法会返回false。这两个案例在下面标记为true和false。

结果

String length 50000, 20 repetitions
Return true 
                 user     system      total        real
scompare     0.620000   0.010000   0.630000 (  0.625711)
hcompare     0.840000   0.010000   0.850000 (  0.845548)
Return false 
                 user     system      total        real
scompare     0.530000   0.000000   0.530000 (  0.532666)
hcompare     1.370000   0.000000   1.370000 (  1.366293)
String length 100000, 20 repetitions
Return true 
                 user     system      total        real
scompare     1.420000   0.100000   1.520000 (  1.516580)
hcompare     2.280000   0.010000   2.290000 (  2.284189)
Return false 
                 user     system      total        real
scompare     1.020000   0.010000   1.030000 (  1.034887)
hcompare     1.960000   0.000000   1.960000 (  1.962655)
String length 500000, 20 repetitions
Return true 
                 user     system      total        real
scompare    10.310000   0.540000  10.850000 ( 10.850988)
hcompare     9.960000   0.180000  10.140000 ( 10.153366)
Return false 
                 user     system      total        real
scompare     8.120000   0.570000   8.690000 (  8.687847)
hcompare     9.160000   0.030000   9.190000 (  9.189997)

结论

如您所见，true sort当n => 500,000 .即使在那里，胜利的差距也相当小，比大多数其他基准比较的相对差异要小得多，在这些比较中，标准方法取得了胜利。虽然哈希计数方法在不同的测试中可能表现得更好，但传统的排序方法似乎很难被击败。

这个答案很有趣吗？我不确定，但由于在看到结果之前我已经完成了大部分工作（我预计这会有利于计数哈希），我决定继续把它拿出来。