As a part of a larger problem I have to solve the following::


*input - number of variables (say n=4)
*input - 'n' numbers in decimal (say 1,3,5,7)
*I need to check for all the grey code neighbours
i.e, to say, 2=00000001(a fixed length string) and
3=00000011(a fixed length string) differ EXACTLY IN ONE BIT.
so they form gery code neighbours and form a duet 000000x1.

* for the above example we get 4 gery code neighbours (so 4 duets)
which are 0000001x (from 1 and 3),
00000x01 (from 1 and 5),
00000x11 (from 3 and 7),
000001x1 (from 5 and 7)


*now I need to combine all the duets. for eg (1 and 5) and (3 and 7) combine to give a QUAD 000000xx1.()
for the above example we get 2 quads--which turn our to be the same.

*now I need to combine the quads to get 8's

* I need to go on and create lists of 1)all singletons
2)all duets
3)all quads
and so on.

so far I've managed to read the inputs and save them in a list of strings ,each string representing one input in binary

i.e, list of 00000001, 00000011, 00000101, 00000111 as strings.

Iam not able to decide how to proceed.
This is the first time Iam writing anything so complex.(I haven't written codes for anything more than sorting numbers before.)This one is for an assignment.
Iam not able to decide what data structures to use

Plz suggest any good way of approaching the problem.

anyone who can help Plz send me an yahoo msg and I'll show u the code I've written so far. Hope U unaderstand .I don't want to post the code.some of my friends too are using this forum.

Arjun.

YAHOO ID: arjunarikeri

Basically you're looking at a fancy table lookup. Build a table of Gray codes for however many bits you're comparing and then look for two adjacent numbers in the list that match the codes in your table. Repeat until your computer chokes and dies.

One easy way to build a Gray code table is to start with a hard coded table for two bits:

00, 01, 11, 10

Copy and reverse the table:

10, 11, 01, 00

Prefix the codes in the first table with 0:

000, 001, 011, 010

Prefix the codes in the second table with 1:

110, 111, 101, 100

Append the second table to the first:

000, 001, 011, 010, 110, 111, 101, 100

This can be used for a table up to as many bits as you want, but keep in mind that there are multiple permutations for Gray codes. Your program specification is vague enough that keeping to it will be very difficult. This in particular is disturbing:

1)all singletons
2)all duets
3)all quads
and so on.

;)

lsiten I already have a 100 line code.
Just that Iam not able to proceed further.But I don't want to post it for everyone to view.

Plz tell me how I can show u my code.

Arjun.

>I already have a 100 line code.
Search google and you may find a clever algorithm to do what you want. Otherwise you're looking at brute force, and that's going to be sloooooooow.

>Plz tell me how I can show u my code.
Here, or nowhere. Daniweb is a public forum. If you want private help that may or may not be good quality (because it isn't publicly checked by the helper's peers), try www.allexperts.com.

>I already have a 100 line code.
Search google and you may find a clever algorithm to do what you want. Otherwise you're looking at brute force, and that's going to be sloooooooow.

>Plz tell me how I can show u my code.
Here, or nowhere. Daniweb is a public forum. If you want private help that may or may not be good quality (because it isn't publicly checked by the helper's peers), try www.allexperts.com.

OK. I'll risk it!
maybe this looks a brute force way.But ,you see, Ican't change it now.
I have an error in the function 'compare'(atleast I feel that the error there)

#include<iostream>
#include<string>
#include<stdlib.h>
#include<list>
#include <sstream>
using namespace std;
// all variables used are global
int n;//number of variables
int m;//number of minterms
int d;//number of don't cares
int i;//used for indexing again and again
int pos;//the functions 'compare' and 'hypergen' use this
list<string>::iterator j;//I've used this in various functions
list<string> minterms;// Each string in the  all the lists in this  program is of length 15 ....
list<string> doncares;// and it represents(in binary) a positive  integer less than ((2^15)-1)
list<string> *slists=new list<string>[20];//I've put some big number
                                      //couldn't find a better solution:-(
list<int>    Minterm; //I needed something golbal (and dynamic!) for the minterms
list<int>    Doncare;

//The following are all the functions used.
void hypergen(int i);//This function generates the hypercubes
string dtob(int integer);
string itoa(int num);
bool compare(string one,string two);
int main(){
// Getting all the inputs from the user
    cout<<"enter the number of variables\n";
    cin>>n;
    for(i=0;i<=n;i++){list<string> LISTi;}
    cout<<"\nEnter the number of minterms\n";
    cin>>m;
    cout<<"\nenter the minterms\n";
    int minterm[m];
    for (i=0;i<m;i++){cin>>minterm[i];Minterm.push_back(minterm[i]);}
    cout<<"\nminterms read-OK!\n";
    cout<<"\nEnter the number of don't cares\n";
    cin>>d;
    int doncare[d];
    cout<<"\nenter the don't cares\n";
    for (i=0;i<d;i++){cin>>doncare[i];Doncare.push_back(doncare[i]);}
    cout<<"\ndon't cares read-OK!\n";
// pushing the minterms and don't cares int their lists
    for (i=0;i<m;i++){minterms.push_back(dtob(minterm[i]));slists[0].push_back(*(--minterms.end()));}
    cout<<"\nBinary representation of Minterms pushed to the list 'minterms' and to slists[0]\n";
    for (i=0;i<d;i++){doncares.push_back(dtob(doncare[i]));slists[0].push_back(*(--doncares.end()));}
    cout<<"\nBinary representation of Don't cares pushed to the list 'doncares' and to slists[0]\n";
    cout<<"\n\n";
//Printing the list to check for corrrectness
    for(j=minterms.begin(); j != minterms.end(); ++j) cout << *j << " ";
    cout <<"\nAren't these minterms ?\n"<< endl;
    for(j=doncares.begin(); j != doncares.end(); ++j) cout << *j << " ";
    cout <<"\nAren't these don't cares ?\n"<<endl;
         for(j=slists[0].begin(); j != slists[0].end(); ++j) cout << *j << " ";
    cout <<"\nAren't these (minterms)+(don't cares) ?\n\n"<<endl;

//Now the 'REAL' thing
    for(i=0;i<=n;i++){hypergen(i);}

return 1;

}

/*------------------------------------------------------------------- ---- ---*/
/* The fuction takes in a decinmal integer and returns it binary representation as a atring  */
string dtob(int integer){
     int index,temp,bin;
     int array[15]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
     string BIN;
     if(integer<0 || integer>32767){
           cout<<"\nThe number must be between 0-32767.\nEverything has a limit!";
           cout<<"\nThis program may fail now";
     }
     else{
           index=14;
           while(index>=0){
                  temp=0;
                  if(integer>=array[index]){
                       temp=array[index];
                       integer=integer-temp;
                       bin=1;
                       index--;
                  }
                  else{
                       bin=0;
                       index--;
                  }
                  BIN+=itoa(bin);
           }
     }

return BIN;

}

/*-------------------------------------------------------------------------------*/
/* input is an integer output is the char of that integer
   for eg if input is integer 5 output is char 5  */
string itoa(int num){         //Don't know much about how this function works!
    stringstream converter;
    converter << num;
return converter.str();
}
/*---------------------------------------------------------------------------------*/
/*This function takes in the index of a list and generates all 'next' order hypercubes
  that ara possible by combining exactly two elements of this list ---------------*/
/*All 'next' order hypercubes generated from 'slists[i]' are stored in 'slists[i+1]  */
/*The two terms which combine can be(and are) safely deleted -----------------------*/
void hypergen(int i){         //I don't want 'i' to be changed in this function
bool arjun;
string temp;//temporary string whiched is pushed into slists[i+1]
list<string>::iterator k;
    for(j=slists[i].begin(); j != slists[i].end(); ++j){
       for(k=++j; k!=slists[i].end(); ++k){
          arjun = compare(*j,*k);
          if (arjun){// need to add an element add a hypercube to slist[i+1]

          }
       }
    }
    for(j=slists[i].begin(); j != slists[i].end(); ++j) cout << *j << " ";
       cout <<"\n This is hypercube list no "<<i<<endl;
}

/*-------------Iam fed up  -------------------------------------------------*/
/*funtion returns a valuue 'TRUE' if the input strings differ exactly by one bit  */
bool compare(string one,string two){
int count;
   count=0;//this stores the number of bits in 'one' and 'two' differ
   pos=0;//pos give the position where the strings 'one' and 'two' differ.
   for(i=0; i<=14; i++){
       if(one[i] != two[i]){++count; pos = i;}
   }
   if(count == 1) {return (0<5);} //returning TRUE
   else           {return (0>5);  //returning FALSE

}

plz help me rectify the error.

Arjun
:confused:

can't believe I posted this.

Plz neglect my previous posting. I had just missed a ' } '.
the error actually got me goin nuts!

Iam sorry,

Arjun

Hi,

suppose 'a' , 'b' and 'c' are three strings which are already storing something.
how can I 1)erase c and
2)combine parts of 'a' and 'b' and store it ic c.


eg: initially a = "helloarjun"
b= "hisam"
c= "how r u"

finally I want c= "hellosam"


thanks in advance

Arjun

Iam screwing up in the function 'hypergen' .Iam not able to use the increment operator properly. i.e, Iam not able to apply ++j /j++ properly.Iam totally confused

Plz read the first posting of this thread for the problem statement.

here is my code

#include<iostream>
#include<string>
#include<stdlib.h>
#include<list>
#include <sstream>
using namespace std;
// all variables used are global
int n;//number of variables
int m;//number of minterms
int d;//number of don't cares
int i;//used for indexing again and again
int pos;//the functions 'compare' and 'hypergen' use this
list<string>::iterator j;//I've used this in various functions
list<string> minterms;// Each string in the  all the lists in this  program is of length 15 ....
list<string> doncares;// and it represents(in binary) a positive  integer less than ((2^15)-1)
list<string> *slists=new list<string>[20];//I've put some big number
                                      //couldn't find a better solution:-(
list<int>    Minterm; //I needed something golbal (and dynamic!) for the minterms
list<int>    Doncare;

//The following are all the functions used.
void hypergen(int i);//This function generates the hypercubes
string dtob(int integer);
string itoa(int num);
bool compare(string one,string two);
int main(){
// Getting all the inputs from the user
    cout<<"enter the number of variables\n";
    cin>>n;
    for(i=0;i<=n;i++){list<string> LISTi;}
    cout<<"\nEnter the number of minterms\n";
    cin>>m;
    cout<<"\nenter the minterms\n";
    int minterm[m];
    for (i=0;i<m;i++){cin>>minterm[i];Minterm.push_back(minterm[i]);}
    cout<<"\nminterms read-OK!\n";
    cout<<"\nEnter the number of don't cares\n";
    cin>>d;
    int doncare[d];
    cout<<"\nenter the don't cares\n";
    for (i=0;i<d;i++){cin>>doncare[i];Doncare.push_back(doncare[i]);}
    cout<<"\ndon't cares read-OK!\n";
// pushing the minterms and don't cares int their lists
    for (i=0;i<m;i++){minterms.push_back(dtob(minterm[i]));slists[0].push_back(*(--minterms.end()));}
    cout<<"\nBinary representation of Minterms pushed to the list 'minterms' and to slists[0]\n";
    for (i=0;i<d;i++){doncares.push_back(dtob(doncare[i]));slists[0].push_back(*(--doncares.end()));}
    cout<<"\nBinary representation of Don't cares pushed to the list 'doncares' and to slists[0]\n";
    cout<<"\n\n";
//Printing the list to check for corrrectness
    for(j=minterms.begin(); j != minterms.end(); ++j) cout << *j << " ";
    cout <<"\nAren't these minterms ?\n"<< endl;
    for(j=doncares.begin(); j != doncares.end(); ++j) cout << *j << " ";
    cout <<"\nAren't these don't cares ?\n"<<endl;
    for(j=slists[0].begin(); j != slists[0].end(); ++j) cout << *j << " ";
    cout <<"\nAren't these (minterms)+(don't cares) ?\n\n"<<endl;

//Now the 'REAL' thing
    for(i=0;i<=n;i++){hypergen(i);}

return 1;

}

/*------------------------------------------------------------------- ---- ---*/
/* The fuction takes in a decinmal integer and returns it binary representation as a atring  */
string dtob(int integer){
     int index,temp,bin;
     int array[15]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
     string BIN;
     if(integer<0 || integer>32767){
           cout<<"\nThe number must be between 0-32767.\nEverything has a limit!";
           cout<<"\nThis program may fail now";
     }
     else{
           index=14;
           while(index>=0){
                  temp=0;
                  if(integer>=array[index]){
                       temp=array[index];
                       integer=integer-temp;
                       bin=1;
                       index--;
                  }
                  else{
                       bin=0;
                       index--;
                  }
                  BIN+=itoa(bin);
           }
     }

return BIN;

}

/*-------------------------------------------------------------------------------*/
/* input is an integer output is the char of that integer
   for eg if input is integer 5 output is char 5  */
string itoa(int num){         //Don't know much about how this function works!
    stringstream converter;
    converter << num;
return converter.str();
}

/*---------------------------------------------------------------------------------*/
/*This function takes in the index of a list and generates all 'next' order hypercubes
  that ara possible by combining exactly two elements of this list ---------------*/
/*All 'next' order hypercubes generated from 'slists[i]' are stored in 'slists[i+1]  */
/*The two terms which combine can be(and are) safely deleted -----------------------*/
void hypergen(int i){         //I don't want 'i' to be changed in this function
bool arjun;
string x ("x");
string temp;//temporary string whiched is pushed into slists[i+1]
list<string>::iterator k;
    for(j=slists[i].begin(); j != slists[i].end(); j++){ //THE ERROR IS SOMEWHERE HERE.
       for(k=j++; k!=slists[i].end(); k++)  {   //A double loop to compare each pair of strings.
          arjun = compare(*j,*k);// 'arjun' is true only when *j and *k differ exactly by 1 bit
          if (arjun){// need to add an element add a hypercube to slist[i+1]
             temp = *j;
             temp[pos] = x[0];
             slists[i+1].push_back(temp);
          }
       }
    }
    for(j=slists[i+1].begin(); j != slists[i+1].end(); j++) cout << *j << " ";
       cout <<"\n This is hypercube list no "<<i+1<<endl;
}

/*-------------Iam fed up  -------------------------------------------------*/
/*funtion returns a valuue 'TRUE' if the input strings differ exactly by one bit  */
bool compare(string one,string two){
int count;
   count=0;//this stores the number of bits in 'one' and 'two' differ
   pos=0;//pos keeps track of position where 'one' and 'two' differ
   cout<<"\n one = "<< one ;        // this is to check weather strings are passeed properly or not
   cout<<"\n two = "<< two <<"\n" ;
   for(i=0; i<=14; i++){
       if(one[i] != two[i]){++count; pos = i;} //for every disimilarity,increase the count by 1

   }
   if(count == 1) {return (0<5);} //returning TRUE
   else           {return (0>5);}  //returning FALSE

}

have a small correction to make in my previous posting.

line no.7 and line no.109 of the code should not have been there. Both are comments which are actually false.I forgot to delete them

very sorry for this


Arjun
Edit/Delete Message

This article has been dead for over six months. Start a new discussion instead.