生成组合，通过组合相邻字符。

huangapple
go评论118阅读模式
英文:

Generate combinations by combining adjacent characters

问题

我有一个程序，应该生成所有可能的相邻字符连接的组合。

例如：

  1. 输入 = [a, b, c]
  2. 输出 = [a, b, c], [ab, c], [a, bc]
  4. 输入 = [a, b, c, d]
  5. 输出 = [a, b, c, d], [ab, c, d], [a, bc, d], [a, b, cd], [ab, cd]
  7. 输入 = [a, b, c, d, e]
  8. 输出 = [a, b, c, d, e], [ab, c, d, e], [a, bc, d, e], [a, b, cd, e], [a, b, c, de], [ab, cd, e], [a, bc, de], **[ab, c, de]**
  9. 我的程序输出缺少最后一个

基本上，我们只允许组合两个相邻字符。

我写了下面的程序。

  1. public class Program
  2. {
  3.     public static void Main(string[] args)
  4.     {
  5.         List<string> cases = new List<string> {"a b c", "a b c d", "a b c d e"};
  6.         for (int c = 0; c < cases.Count; c++)
  7.         {
  8.             var result = F(cases[c]);
  9.             Console.WriteLine(cases[c]);
  10.             result.ForEach(Console.WriteLine);
  11.             Console.WriteLine("---------------------------");
  12.         }
  13.     }
  15.     public static List<string> F(string searchTerm)
  16.     {
  17.         List<string> result = new List<string>();
  18.         var terms = searchTerm.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
  19.         if (terms.Count == 1)
  20.             return new List<string> { searchTerm };
  22.         for (int x = 1; x <= 2; x++)
  23.         {
  24.             for (int i = 0; i < terms.Count - 1; i++)
  25.             {
  26.                 if (x == 1)
  27.                 {
  28.                     int j = i;
  29.                     var joinedWord = terms[j] + terms[j + 1];
  30.                     result.Add(searchTerm.Replace($"{terms[j]} {terms[j + 1]}", joinedWord));
  31.                 }
  33.                 if (x == 2)
  34.                 {
  35.                     int j = i;
  36.                     if (j + 3 < terms.Count)
  37.                     {
  38.                         var firstJoinedWord = terms[j] + terms[j + 1];
  39.                         var secondJoinedWord = terms[j + 2] + terms[j + 3];
  40.                         result.Add(searchTerm.Replace($"{terms[j]} {terms[j + 1]} {terms[j + 2]} {terms[j + 3]}", firstJoinedWord + " " + secondJoinedWord));
  41.                     }
  42.                 }
  43.             }
  44.         }
  46.         return result;
  47.     }
  48. }

以下是输出。

生成组合，通过组合相邻字符。

我不知道是否需要使用递归/动态规划来解决这个问题，因为可能会有N种组合。任何帮助将不胜感激。谢谢。

英文:

I have a program that should generate combinations of concatenation of all possible adjacent characters.

For example

  1. Input = [a,b,c]
  2. Output = [a,b,c], [ab,c], [a,bc]
  4. Input = [a,b,c,d]
  5. Output = [a,b,c,d], [ab,c,d], [a,bc,d], [a,b,cd], [ab,cd]
  7. Input = [a,b,c,d,e]
  8. Output = [a,b,c,d,e], [ab,c,d,e], [a,bc,d,e], [a,b,cd,e], [a,b,c,de], [ab,cd,e], [a,bc,de], **[ab,c,de]**
  9. Last one missing from my program output

Basically we are only allowed to combine two adjacent characters.

I have written the program below.

  1. public class Program
  2. {
  3.     public static void Main(string[] args)
  4.     {
  5.         List&lt;string&gt; cases = new List&lt;string&gt; {&quot;a b c&quot;, &quot;a b c d&quot;, &quot;a b c d e&quot;};
  6.         for (int c = 0; c &lt; cases.Count; c++)
  7.         {
  8.             var result = F(cases[c]);
  9.             Console.WriteLine(cases[c]);
  10.             result.ForEach(Console.WriteLine);
  11.             Console.WriteLine(&quot;---------------------------&quot;);
  12.         }
  13.     }
  15.     public static List&lt;string&gt; F(string searchTerm)
  16.     {
  17.         List&lt;string&gt; result = new List&lt;string&gt;();
  18.         var terms = searchTerm.Split(new[] { &#39; &#39; }, StringSplitOptions.RemoveEmptyEntries).ToList();
  19.         if (terms.Count == 1)
  20.             return new List&lt;string&gt; { searchTerm };
  22.         for (int x = 1; x &lt;= 2; x++)
  23.         {
  24.             for (int i = 0; i &lt; terms.Count - 1; i++)
  25.             {
  26.                 if (x == 1)
  27.                 {
  28.                     int j = i;
  29.                     var joinedWord = terms[j] + terms[j + 1];
  30.                     result.Add(searchTerm.Replace($&quot;{terms[j]} {terms[j + 1]}&quot;, joinedWord));
  31.                 }
  33.                 if (x == 2)
  34.                 {
  35.                     int j = i;
  36.                     if (j + 3 &lt; terms.Count)
  37.                     {
  38.                         var firstJoinedWord = terms[j] + terms[j + 1];
  39.                         var secondJoinedWord = terms[j + 2] + terms[j + 3];
  40.                         result.Add(searchTerm.Replace($&quot;{terms[j]} {terms[j + 1]} {terms[j + 2]} {terms[j + 3]}&quot;, firstJoinedWord + &quot; &quot; + secondJoinedWord));
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.         
  47.         return result;
  48.     }
  49. }

And here is the output.

生成组合，通过组合相邻字符。

I don't know if we need to use Recursion/Dynamic Programming to solve this? because there can be N number of combinations. Any help will be appreciated. Thanks.

答案1

得分: 1

以下是翻译好的代码部分：

  1. arr = ["a", "b", "c", "d", "e"]
  3. possibilities = []
  5. def generate_combinations(combination, index):
  6.     global arr
  7.     if index == len(arr):
  8.         possibilities.append(list(combination))
  9.     else:
  10.         # Either we can concatenate with our adjacent
  11.         if index < len(arr) - 1:
  12.             generate_combinations(combination + [arr[index] + arr[index+1]], index+2)
  13.         # Or we don't
  14.         generate_combinations(combination + [arr[index]], index+1)
  16. generate_combinations([], 0)
  18. for p in possibilities:
  19.     print(p)

输出的测试案例结果：

  1. ['ab', 'cd', 'e']
  2. ['ab', 'c', 'de']
  3. ['ab', 'c', 'd', 'e']
  4. ['a', 'bc', 'de']
  5. ['a', 'bc', 'd', 'e']
  6. ['a', 'b', 'cd', 'e']
  7. ['a', 'b', 'c', 'de']
  8. ['a', 'b', 'c', 'd', 'e']
  9. [Finished in 40ms]
英文:

Check out this code

  1. arr = [&quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;d&quot;, &quot;e&quot;]
  4. possibilities = []
  6. def generate_combinations(combination, index):
  7.     global arr
  8.     if index == len(arr):
  9.         possibilities.append(list(combination))
  10.     else:
  11.         # Either we can concatenate with our adjacent
  12.         if index &lt; len(arr) - 1:
  13.             generate_combinations(combination + [arr[index] + arr[index+1]], index+2)
  14.         # Or we don&#39;t
  15.         generate_combinations(combination + [arr[index]], index+1)
  17. generate_combinations([], 0)
  20. for p in possibilities:
  21.     print(p)

Output for your test case:

  1. [&#39;ab&#39;, &#39;cd&#39;, &#39;e&#39;]
  2. [&#39;ab&#39;, &#39;c&#39;, &#39;de&#39;]
  3. [&#39;ab&#39;, &#39;c&#39;, &#39;d&#39;, &#39;e&#39;]
  4. [&#39;a&#39;, &#39;bc&#39;, &#39;de&#39;]
  5. [&#39;a&#39;, &#39;bc&#39;, &#39;d&#39;, &#39;e&#39;]
  6. [&#39;a&#39;, &#39;b&#39;, &#39;cd&#39;, &#39;e&#39;]
  7. [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;de&#39;]
  8. [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;d&#39;, &#39;e&#39;]
  9. [Finished in 40ms]

Let me know if the solution isn't understandable

答案2

得分: 0

以下是您要的中文翻译：

  1. using System;
  2. using System.Linq;
  3. using System.Collections.Generic;
  5. class Program
  6. {
  7.     public static IEnumerable<List<string>> Mates(List<string> t)
  8.     {
  9.         if (t.Count == 0)
  10.         {
  11.             yield return new List<string> {};
  12.             yield break;
  13.         }
  14.     
  15.         if (t.Count == 1)
  16.         {
  17.             yield return t;
  18.             yield break;
  19.         }
  20.         
  21.         foreach (var m in Mates(t.GetRange(1, t.Count - 1)))
  22.             yield return new List<string> { t[0] }
  23.                 .Concat(m)
  24.                 .ToList();
  25.         
  26.         foreach (var m in Mates(t.GetRange(2, t.Count - 2)))
  27.             yield return new List<string> { Mate(t[0], t[1]) }
  28.                 .Concat(m)
  29.                 .ToList();
  30.     }
  31.     
  32.     public static string Mate(string a, string b)
  33.     {
  34.         return a + b;
  35.     }
  36.     
  37.     public static void Main(string[] args)
  38.     {
  39.         var input = new List<string> { "a", "b", "c", "d", "e" };
  40.         
  41.         foreach (var m in Mates(input))
  42.             Console.WriteLine(string.Join(",", m));
  43.     }
  44. }

希望这个翻译对您有所帮助。

英文:

Here's a quick JavaScript version that you can run in your browser to verify the result -

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. function *mates(t) {
  2.   if (t.length == 0) return yield []
  3.   if (t.length == 1) return yield t
  4.   for (const m of mates(t.slice(1)))
  5.     yield [t[0], ...m]
  6.   for (const m of mates(t.slice(2)))
  7.     yield [mate(t[0], t[1]), ...m]
  8. }
  10. function mate(a,b) {
  11.   return a + b
  12. }
  14. for (const m of mates([&quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;d&quot;, &quot;e&quot;]))
  15.   console.log(m.join(&quot;,&quot;))

<!-- language: lang-css -->

  1. .as-console-wrapper { min-height: 100%; top: 0; }

<!-- end snippet -->

  1. a,b,c,d,e
  2. a,b,c,de
  3. a,b,cd,e
  4. a,bc,d,e
  5. a,bc,de
  6. ab,c,d,e
  7. ab,c,de
  8. ab,cd,e

We can easily convert that to a C# program -

  1. using System;
  2. using System.Linq;
  3. using System.Collections.Generic;
  5. class Program
  6. {
  7.     public static IEnumerable&lt;List&lt;string&gt;&gt; Mates(List&lt;string&gt; t)
  8.     {
  9.         if (t.Count == 0)
  10.         {
  11.             yield return new List&lt;string&gt; {};
  12.             yield break;
  13.         }
  14.     
  15.         if (t.Count == 1)
  16.         {
  17.             yield return t;
  18.             yield break;
  19.         }
  20.         
  21.         foreach (var m in Mates(t.GetRange(1, t.Count - 1)))
  22.             yield return new List&lt;string&gt; { t[0] }
  23.                 .Concat(m)
  24.                 .ToList();
  25.         
  26.         foreach (var m in Mates(t.GetRange(2, t.Count - 2)))
  27.             yield return new List&lt;string&gt; { Mate(t[0], t[1]) }
  28.                 .Concat(m)
  29.                 .ToList();
  30.     }
  31.     
  32.     public static string Mate(string a, string b)
  33.     {
  34.         return a + b;
  35.     }
  36.     
  37.     public static void Main(string[] args)
  38.     {
  39.         var input = new List&lt;string&gt; { &quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;d&quot;, &quot;e&quot; };
  40.         
  41.         foreach (var m in Mates(input))
  42.             Console.WriteLine(string.Join(&quot;,&quot;, m));
  43.     }
  44. }
  1. a,b,c,d,e
  2. a,b,c,de
  3. a,b,cd,e
  4. a,bc,d,e
  5. a,bc,de
  6. ab,c,d,e
  7. ab,c,de
  8. ab,cd,e

huangapple
  • 本文由 发表于 2023年6月1日 19:45:49
  • 转载请务必保留本文链接：https://go.coder-hub.com/76381541.html
  • algorithm
  • c#
  • combinations
  • dynamic-programming
  • recursion
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定