尝试获取二进制数组中的每个可能的子字符串

Question

我不太确定标题的措辞，所以请原谅我。

实际上，我正在从事一个变得相当复杂的项目，因此我正在削减大量代码以使其更快、更易于使用。

这就是上下文，这就是问题所在。我必须在一个字符串中找到所有可能的二进制数字子串。这样解释可能更容易：

我需要什么功能：

输入：“2”
- 输出：“00 01 10 11”
输入：“3”
- 输出：“000 001 010 011 100 101 110 111”

我已经可以相当轻松地使用类似的东西：

String getAllPossibleOutcomes(int substringLength) {
  String result = "";
  for(int i = 0; i < Math.Pow(2,substringLength); i++) {
    String tempStr = "";
    for(int bitInQuestion = 0; bitInQuestion < substringLength; bitInQuestion++) {
      tempStr = ConvertIntToBinary(i).GetBit(bitInQuestion).ToString();
    }
    result += tempStr;
  }
  return result;
}

^ 顺便说一句，这是目前的伪代码，只是在我实际编写之前大致弄清楚如何做某事。

此代码有效，因为 getAllPossibleOutcomes(3) 输出：

000001010011100101110111

完全正确。但是，按照我构建代码的方式，有没有办法通过将每组 3 位数字作为单独的解决方案来缩短代码？

例如

000 001 010

可以读作

000 ___ ___
00 0_ ___
_0 00 ___
___001___
___ 01 0_
____1 01
___ ___ 010

如您所见，在这种情况下，我要退出：“000,000,000,001,010,101,010”，其中涉及很多加倍。

有什么算法可以做到这一点吗？即使只是一篇维基百科文章或我可以开始研究的东西？我肯定不是第一个尝试过这样的人吧？

只是手动，我想像“00110”这样的东西可以用于 2 宽选项，从那时起你从左到右得到 00,01,11,10，但我想要一些可以做的事情这适用于任意长度的数字。正如您可能想象的那样，只要我做了 20 位长这样的事情，早期的“尝试所有可能的组合”技术就会变得非常快。

我不知道这是一道编程题还是一道数学题。

我知道这是一个非常不寻常的问题，我非常感谢任何能帮助我的人，即使它是给我一个算法的名称。即使只是我可以研究的起点也是光荣的。

亲切的问候，安德烈

Answer 1

我不确定我是否正确理解了你的问题。

很明显，有许多不同的解决方案可以将小数转换为二进制字符串。因此，我们可以为此编写一个超简单的函数，并使用不同的函数进行分组。

也许像下面这样？

#include <iostream>
#include <string>

std::string toBin(unsigned int n, const unsigned int numberOfDigits) {
    std::string binString(numberOfDigits, '0');
    while (n) {
        binString = (n % 2 == 0 ? "0" : "1") + binString; 
        n /= 2;
    }
    return binString.substr(0,numberOfDigits);
}

void showGroups(const unsigned int numberOfDigits) {
    for (unsigned int i{}; i < (1u << numberOfDigits); ++i)
        std::cout << toBin(i, numberOfDigits) << '\n';
}

int main() {
    for (unsigned int test = 1; test < 5; ++test) {
        showGroups(test);
        std::cout << "\n\n";
    }
}

请在评论中写下，如果我误解了你的问题并帮助澄清它，那么我会提供另一个答案。

Answer 2

我结合了上面评论中列出的一些信息，尤其是维基百科中的信息，给出了一个 python 代码，我将其改编为 C#。 Concatenate 方法来自 SO。请注意，原始 python 代码更强大，因为它可以管理任何对象集，而不仅仅是零和一。

在这里，作为控制台应用程序：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace de_bruiyn
{
    class Program
    {
        static readonly int[] alphabet = { 0, 1 };
        static int k;
        static int n;
        static List<int> a;
        static List<int> sequence;

        static void Main()
        {
            a = new List<int>();
            sequence = new List<int>();
            Console.WriteLine("Length of the binary numbers : ");
            string s = Console.ReadLine();
            n = Int32.Parse(s);
            k = alphabet.Length;

            Console.WriteLine(De_bruijn(n).Concatenate<int>(""));
            Console.ReadKey();
        }

        public static List<int> De_bruijn(int n)
        {
            for (int i = 0; i < n * k; i++)
            {
                a.Add(0);
            }                
            
            Db(1, 1);

            return sequence;
        }

        private static void Db(int t, int p)
        {
            if (t > n)
            {
                if (n % p == 0)
                {
                    sequence.AddRange(a.GetRange(1, p));
                }
            }
            else
            {
                a[t] = a[t - p];
                Db(t + 1, p);
                foreach (var j in Enumerable.Range(a[t - p] + 1, k - (a[t - p] + 1)))
                {
                    a[t] = j;
                    Db(t + 1, t);
                }
            }
        }

       
    }
    static class Toto
    {
        public static string Concatenate<T>(this IEnumerable<T> source, string delimiter)
        {
            var s = new StringBuilder();
            bool first = true;
            foreach (T t in source)
            {
                if (first)
                {
                    first = false;
                }
                else
                {
                    s.Append(delimiter);
                }
                s.Append(t);
            }
            return s.ToString();
        }
    }
}

精确的维基百科 link 与 python 代码：https://en.wikipedia.org/wiki/De_Bruijn_sequence

请注意，结果字符串是循环的，即当 n = 2 时，结果为 0011，因为如果你到达第二个也是最后一个“1”，你也必须取第一个“0”。如果您不想那样做，只需在此结果的末尾添加字符串结果的前 n - 1 个字符即可完成它。

尝试获取二进制数组中的每个可能的子字符串

Attempting to get every possible substring in binary array

c#

c++

math