Solved

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

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

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Introduction Although it is an old technology, serial ports are still being used by many hardware manufacturers. If you develop applications in C#, Microsoft .NET framework has SerialPort class to communicate with the serial ports.  I needed to…
This article is for Object-Oriented Programming (OOP) beginners. An Interface contains declarations of events, indexers, methods and/or properties. Any class which implements the Interface should provide the concrete implementation for each Inter…
This tutorial demonstrates a quick way of adding group price to multiple Magento products.
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

746 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now