如何在 ruby 中生成部分重复的排列？

Question

我有一个数字范围 R = (1..n)。我还有一个角色'a'。我想生成长度为 L (L > n + 2) 的字符串，所有数字的顺序都相同，但要通过 'a' 的每个重复排列来填充长度 L。例如，如果 n = 3 和 L = 7，那么一些有效的字符串将是：

"123aaaa",
"1a23aaa",
"1aa2a3a",
"aaaa123"

而以下字符串无效：

"213aaaa", # invalid, because 1,2,3 are not in order
"123a", #invalid, because length < L
"1123aaa", # invalid because a number is repeated

我目前正在这样做，效率太低了：

n = 3
L = 7
all_terms = (1..n).to_a + Array.new(L - n, 'a')
all_terms.permutation.each do |permut|
  if(valid_permut? permut) # checks if numbers are in their natural order
    puts permut.join
  end
end

如何更有效地直接生成有效字符串？

Answer 1

问题等价于：select n 个索引 0 到 L - 1 的元素，用 1 到 n 填充这些元素相应地，并用一些常量字符填充其余部分。

在您的示例中，它从 0..6:

中获取 3 个元素

(0..6).to_a.combination(3).to_a
 => [[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 1, 5], [0, 1, 6], [0, 2, 3], [0, 2, 4],
 [0, 2, 5], [0, 2, 6], [0, 3, 4], [0, 3, 5], [0, 3, 6], [0, 4, 5], [0, 4, 6], [0, 5, 6], 
 [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 4], [1, 3, 5], [1, 3, 6], [1, 4, 5],
 [1, 4, 6], [1, 5, 6], [2, 3, 4], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6], [2, 5, 6],
 [3, 4, 5], [3, 4, 6], [3, 5, 6], [4, 5, 6]]

这里的每一个子数组代表一个可能的结果。例如，[0, 2, 3] 对应于 '0a12aaa'，[3, 5, 6] 对应于 'aaa0a12'，等等。这种转换的代码很简单。

Answer 2

您可以将其建模为两个字符串的所有可能交错，其中保留输入元素的相对顺序。这是一个递归解决方案。它的工作原理是从一个列表中选择一个元素，并将其添加到所有可能的子问题之前，然后在从第二个列表中选择一个元素的地方再次执行此操作，并在最后组合两个解决方案集。

# Returns an array of all possible interleaving of two strings
# Maintains relative order of each character of the input strings
def interleave_strings_all(a1, a2)
    # Handle base case where at least one input string is empty
    return [a1 + a2] if a1.empty? || a2.empty?

    # Place element of first string, and prepend to all subproblems
    set1 = interleave_strings_all(a1[1..-1], a2).map{|x| a1[0] + x}
    # Place element of second string and prepend to all subproblems
    set2 = interleave_strings_all(a1, a2[1..-1]).map{|x| a2[0] + x}

    # Combine solutions of subproblems into overall problem
    return set1.concat(set2)    
end


if __FILE__ == [=10=] then
    l = 5
    n = 3
    a1 = (1..n).to_a.map{|x| x.to_s}.join()
    a2 = 'a' * (l - n)
    puts interleave_strings_all(a1, a2)
end

输出为：

 123aa
 12a3a
 12aa3
 1a23a
 1a2a3
 1aa23
 a123a
 a12a3
 a1a23
 aa123

如何在 ruby 中生成部分重复的排列？

How to generate partially repeated permutations in ruby?

ruby

algorithm

permutation