Solved

How to Generate a "2-to-the-n" Array of Binary Vectors?

Posted on 2006-06-14
3
288 Views
Last Modified: 2010-04-16
Hello-

I have a need to generate vectors of 1s and 0s for an application I'm building.  The code below takes a number (currently hardcoded to 14) and prints out the binary representation of each integer from 1 to 2 to the 14th power.  Basically I know there are 2 to the n possible combinations of 1s and 0s for any given n, but what's stumping me is that I want all of the combinations to have n members (ie if n = 5, 00000, 01000, 01100 and 11111 are all acceptable, but 1001, the binary representation of the integer 9, doesn't have 5 digits.  I want to get 2 to the n solutions, each one of which has n digits, either a 1 or a 0.  For what I'm trying to do, I don't care that 00000, for instance, is not a binary representation of some integer.  I just care that it's a possible combination of 1s and 0s of length 5.  Please help!


using System;
using System.Collections.Generic;
using System.Text;

namespace Binary
{
    class Program
    {
        static void Main(string[] args)
        {
            int depth = 14;
            Dictionary<int, BinarySolution> allSolutions = new Dictionary<int, BinarySolution>();

            for (int i = 1; i <= Math.Pow(2, depth); i++)
            {
                //There are "2 to the 'depth' " possible solutions,
                //and the binary representation of each integer is the actual solution.
               
                //So if we have 14 stocks to work with (which at this point would already be sorted)
                //which could go either way (1=UP or 0=DOWN) with respect to the nearest round lot.
                //let's call the furthest one away 1, and the closest 14. (Sorted high to low).

                //To get the best one, we need to check every combination.
                allSolutions.Add(i, new BinarySolution(i));

                ConvertDecimalToBinary(i);
                Console.Write(" : ");

                Console.WriteLine(i.ToString());
                Console.ReadLine();
                for (int j = 1; j <= depth; j++)
                {
                   

                }
            }
            Console.ReadLine();

            foreach (int b in allSolutions.Keys)
            {

                Console.Write(allSolutions[b].theNumber.ToString() + " : ");
                foreach (char i in allSolutions[b].nums)
                {
                    Console.Write(i);
                }
                Console.WriteLine();
            }

            Console.ReadLine();
        }
        static void ConvertDecimalToBinary(int number)
        {
            int tempValue = 0;
            int intNum = 0;

            System.Text.StringBuilder binaryValue = new System.Text.StringBuilder();

            intNum = number;
            do
            {
                tempValue = intNum % 2;
                binaryValue.Append(tempValue.ToString());
                intNum = intNum / 2;

            } while (intNum != 0);

            char[] c = binaryValue.ToString().ToCharArray();
            Array.Reverse(c);
            string result = new string(c);
            Console.Write(result);
            Console.Write(" : " + result.Length.ToString());
            //Assert.IsTrue(Convert.ToInt32(result, 2) == integerNumber, "Base10 Conversion To Base2");

        }
    }
    public class BinarySolution
    {
        public int theNumber;
        public List<char> nums;

        public BinarySolution(int number)
        {
            this.theNumber = number;
            int tempValue = 0;
            int intNum = 0;

            System.Text.StringBuilder binaryValue = new System.Text.StringBuilder();

            intNum = number;
            do
            {
                tempValue = intNum % 2;
                binaryValue.Append(tempValue.ToString());
                intNum = intNum / 2;

            } while (intNum != 0);

            char[] c = binaryValue.ToString().ToCharArray();
            Array.Reverse(c);

            //So this string represents a solution (ie 1010000101010)
            string result = new string(c);

            this.nums = new List<char>();

            foreach (char r in result)
            {
                this.nums.Add(r);
            }
        }
    }
0
Comment
Question by:gurteen
3 Comments
 
LVL 11

Accepted Solution

by:
Expert1701 earned 300 total points
ID: 16906936
The following code:

  int depth = 5;
  for (int i = 0; i < 1 << depth; i++)
  {
    for (int j = depth - 1; j >= 0; j--)
      Console.Write((i >> j) % 2 == 0 ? "0" : "1");

    Console.WriteLine();
  }

Generates the output:

00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111

It is not clear to me how you would like to use these values, but something like this might work:

  int depth = 4;

  bool[][] solutions = new bool[1 << depth][];

  for (int i = 0; i < (1 << depth); i++)
  {
    solutions[i] = new bool[depth];
    for (int j = 0; j < depth; j++)
      solutions[i][j] = (i >> j) % 2 == 1;
  }


  foreach (bool[] solution in solutions)
  {
    Console.WriteLine("Solution:");
    for (int i = 0; i < solution.Length; i++)
      Console.WriteLine(" " + i + " " + (solution[i] ? "1" : "0"));
  }

Which has the output:

Solution:
 1 0
 2 0
 3 0
 4 0
Solution:
 1 1
 2 0
 3 0
 4 0
Solution:
 1 0
 2 1
 3 0
 4 0
Solution:
 1 1
 2 1
 3 0
 4 0
Solution:
 1 0
 2 0
 3 1
 4 0
Solution:
 1 1
 2 0
 3 1
 4 0
Solution:
 1 0
 2 1
 3 1
 4 0
Solution:
 1 1
 2 1
 3 1
 4 0
Solution:
 1 0
 2 0
 3 0
 4 1
Solution:
 1 1
 2 0
 3 0
 4 1
Solution:
 1 0
 2 1
 3 0
 4 1
Solution:
 1 1
 2 1
 3 0
 4 1
Solution:
 1 0
 2 0
 3 1
 4 1
Solution:
 1 1
 2 0
 3 1
 4 1
Solution:
 1 0
 2 1
 3 1
 4 1
Solution:
 1 1
 2 1
 3 1
 4 1
0
 
LVL 85

Assisted Solution

by:Mike Tomlinson
Mike Tomlinson earned 200 total points
ID: 16907521
Here is a generic "counting" system I wrote that gives you the next "number" in the sequence based on a custom character set.  It will theoretically count to any length necessary with no math overflows.

(you can see the original character set of "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" commented out that was used for "batch counter")

Set a var initially to all "0"s filled to your target length.  Then you can simply use a loop to repeated get the next value until the length of the return value exceeds that of the length you need.

This type of system may be useful in other applications.  =)


        private void Form1_Load(object sender, EventArgs e)
        {
            textBox1.Text = "00000";
        }

        private void button1_Click_1(object sender, EventArgs e)
        {
            textBox1.Text = NextBatch(textBox1.Text);
        }

        public String NextBatch(String curBatch)
        {            
            //String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
            String chars = "01";
            Char[] values = chars.ToCharArray();

            // return first character in sequence if nothing passed in
            if ((curBatch == null) || (curBatch.Length == 0))
            {
                return chars.Substring(0, 1);
            }

            // if any of the characters passed in are illegal,
            // then return just the first character in the sequence
            int i;
            curBatch = curBatch.ToUpper();
            for (i = 0; i < curBatch.Length; i++)
            {
                if (chars.IndexOf(curBatch.Substring(i, 1)) == -1)
                {
                    return chars.Substring(0, 1);
                }
            }

            // we had a legal starting batch sequence
            System.Text.StringBuilder Batch = new StringBuilder(curBatch);
            Char curChar = Batch[Batch.Length - 1];
            int index = Array.IndexOf(values, curChar);
            if (index < (chars.Length - 1))
            {
                // only the last character needed to be incremented
                Batch[Batch.Length - 1] = values[++index];
                return Batch.ToString();
            }
            else
            {
                // we had a "carry over"
                // reset the last character and bubble down
                // the carry over as far as it needs to go
                Batch[Batch.Length - 1] = values[0];
                int startPosition = Batch.Length - 2;
                for (i = startPosition; i >= 0; i--)
                {
                    curChar = Batch[i];
                    index = Array.IndexOf(values, curChar);
                    if (index < (values.Length - 1))
                    {
                        // "carry over" has stopped
                        // increment current character
                        Batch[i] = values[++index];
                        return Batch.ToString();
                    }
                    else
                    {
                        // bubble down the "carry over"
                        Batch[i] = values[0];
                    }
                }
                // "carry over" was bubbled thru entire sequence
                // prepend the first character in the sequence
                Batch.Insert(0, values[0]);
                return Batch.ToString();
            }
        }
0
 

Author Comment

by:gurteen
ID: 16908305
This gets me exactly what I need - thank you very much!
0

Featured Post

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In order to hide the "ugly" records selectors (triangles) in the rowheaders, here are some suggestions. Microsoft doesn't have a direct method/property to do it. You can only hide the rowheader column. First solution, the easy way The first sol…
Summary: Persistence is the capability of an application to store the state of objects and recover it when necessary. This article compares the two common types of serialization in aspects of data access, readability, and runtime cost. A ready-to…
A short tutorial showing how to set up an email signature in Outlook on the Web (previously known as OWA). For free email signatures designs, visit https://www.mail-signatures.com/articles/signature-templates/?sts=6651 If you want to manage em…

820 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question