Solved

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

Posted on 2006-06-14
3
287 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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …
With Secure Portal Encryption, the recipient is sent a link to their email address directing them to the email laundry delivery page. From there, the recipient will be required to enter a user name and password to enter the page. Once the recipient …

806 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