I was not entirely sure how to phrase the title, so please forgive me for that.
Effectively, I am working on a project that has become quite complex, so I am cutting down alot of the code to make it quicker and easier to work with.
So that's the context, here's the issue. I have to find every possible substring of binary digits within a string. It may be easier to explain this way:
What function I require:
- Input: "2"
- Output: "00 01 10 11"
- Input: "3"
- Output: "000 001 010 011 100 101 110 111"
That I can already do fairly easily using something like:
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;
}
^ BTW This is Pseudocode for now, just figuring out roughly HOW to do something before I actually write it up.
This code works, since getAllPossibleOutcomes(3) outputs:
000001010011100101110111
which is all correct. However, the way I am structuring my code, is there a way to shorten this by taking each individual set of 3 digits as a seperate solution?
E.g.
000 001 010
could be read as
- 000 ___ ___
- 00 0_ ___
- _0 00 ___
- ___ 001 ___
- ___ 01 0_
- ___ _1 01
- ___ ___ 010
As you can see, in this instance, I am getting out: "000,000,000,001,010,101,010" which involves a lot of double ups.
Is there any algorithm that can do this? Even just a wikipedia article or something I can start looking into? Surely I am not the first person to have tried something like this?
Just manually, I guess something like "00110" could work for the 2 wide option, since then you get 00,01,11,10 as you go from left to right, but I would like something that will do this for an arbitrary length of digits. As you can probably imagine, the earlier technique of "Just try every possible combination" gets big very fast as soon as I do something like 20 digits long.
I have no idea if this is more a programming or a maths question.
I know this is quite an unusual question, and I greatly appreciate anyone who can help me out, even if it's giving me the name of an algorithm. Even just a starting point I can look into would be glorious.
Kind regards, Andrey
CodePudding user response：
I am not sure, if I understand your question correctly.
It is clear that there are many many many different solutions to convert decimals to binary strings. So, we could write an ultra simple function for that and do the grouping with a different function.
Maybe something like the below?
#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";
}
}
Please write in the comment, if I misunderstood your question and help to clarify it, then I will provide another answer.
CodePudding user response：
I combined some info I listed in the comment above, especially one in wikipedia, giving a python code which I adapted to C#. The Concatenate method comes from SO. Note that the original python code is more powerful because it can manage any set of objects, not only zeros and ones.
Here it is, as console app:
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();
}
}
}
Precise wikipedia link with the python code: https://en.wikipedia.org/wiki/De_Bruijn_sequence
PLEASE note that the resulting string is meant to be circular, i.e. when n = 2, the result is 0011 because if you reach the second and final "1" you have to take the first "0" too. If you don't wan't that, just add at the end of this result the n - 1 first chars of the string result to complete it.