Jump to content



Welcome to KnowledgeSutra - Dear Guest , Please Register here to get Your own website. - Ask a Question / Express Opinion / Reply w/o Sign-Up!
- - - - -

How Can I Get Every Possible Combination With One Dimensional Array And Unknown Var[Brute Force]?

Started by Guest_Jasim_*, Aug 19 2010 11:20 AM


3 replies to this topic

#1 Guest_Jasim_*

  • Guests

Posted 19 August 2010 - 11:20 AM

Hello Every one


I have a one dimension array and i want to check for every possible combination of unknown number.

for example if i have a[7];

and i want combination of three lines (not always three)

like..
(a[0],a[1],a[2])
(a[0],a[1],a[3])
(a[0],a[1],a[4])
(a[0],a[1],a[5])
(a[0],a[1],a[6])
(a[0],a[2],a[3])
(a[0],a[2],a[4])
(a[0],a[2],a[5])
(a[0],a[2],a[6])
(a[0],a[3],a[4])
......
......
......
......


(a[4],a[5],a[6])....





I am really sorry but I'm sure my code wont do you any good

and also I'm afraid if I put The whole code you would say it's all wrong

I'm not very good with programming

but here is my problem

I want to implement the Hungarian method to a c++ program

and because I am not a pro I picked the double array for in putting the matrix

one of the steps require to lock number of lines then check for number of zeros if it's true we complete the steps if not we unlock what we locked then lock different lines 




#include <iostream>


using namespace std;

void arrayshow(int a[5][5], int r, int c)
{
         //showing the array
    cout<<"your table is"<<endl;
    cout<<"\t\t";
    for(int j=0; j<c; j++){
            cout<<"Y"<<j+1<<"\t";        
                          }
cout<<endl<<endl;
    for(int i=0; i<r; i++){
            cout<<"        X"<<i+1<<"\t";
         for(int j=0; j<c; j++){
                 cout<<a[i][j]<<"\t";
                               }
         cout<<endl;
                          }
}


int main(){
    
     int r=5;
    int c=5;
    /*
    cout<<"enter rows number"<<endl;
    cin>>r;
    
    cout<<"enter columns number"<<endl;
    cin>>c;
    
    //initiating the array
    int a[100][100];
        for(int i=0; i<100; i++){
            for(int j=0; j<100; j++){
                    a[i][j]=0;                  
                    }
            
            }
    //filling the array
    cout<<"enter costs"<<endl;
    
    for(int i=0; i<r; i++){
           for(int j=0; j<c; j++){
                  cout<<"enter X"<<i+1<<"Y"<<j+1<<"   ";
                   cin>>a[i][j];
                    
                   }
            
         }
      */
  int a[5][5]={10,5,9,18,11,13,19,6,12,14,3,2,4,4,5,18,9,12,17,15,11,6,14,19,10};
            //showing the array
            arrayshow(a,r,c);
            
            
       /*     
    
    cout<<"your table is"<<endl;
    cout<<"\t\t";
                for(int j=0; j<c; j++){
                    cout<<"Y"<<j+1<<"\t";
                    
                    }
    cout<<endl<<endl;
        for(int i=0; i<r; i++){
                cout<<"        X"<<i+1<<"\t";
            for(int j=0; j<c; j++){
                    cout<<a[i][j]<<"\t";
                    
                    }
            cout<<endl;
            }*/
            
            
            
            
            
    //checking for unbalanced
if(c<r){
        int y=r-c;  
        c=c+y;
        }


if(c>r){
        int y=c-r;
        r=r+y;
        }



        
        
    //showing the array
    arrayshow(a,r,c);
    
    //coping the array
    int copy[5][5];
    
    for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                  copy[i][j]=a[i][j];                  
                    }
            }
    
        //showing the array
    cout<<"THE COPIED TABLE IS"<<endl;
   arrayshow(copy,r,c);
 
 
 
 // min or max
    int choice;
    cout<<"please type your choice:     "<<endl;
    cout<<"1- minimization.."<<endl;
    cout<<"2- maximization.."<<endl;
    cin>>choice;
    
    if (choice==2){
       int max=0;
           
       for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                  if(max<copy[i][j])
                  max=copy[i][j];                  
                    }
            } 
            
            
       for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                    copy[i][j]=max-copy[i][j];                  
                    }
            } 
       //showing the array
    cout<<"maximization after fixing"<<endl;
   arrayshow(copy,r,c);      
                   } 


   
   //first table
      int min[r];
      for(int i=0; i<r; i++){ 
          min[i]=copy[i][0];
            for(int j=0; j<c; j++){
                   
                   if( min[i]>copy[i][j])
                   min[i]=copy[i][j];                
                    }
             for(int j=0; j<c; j++){
                  copy[i][j]=copy[i][j]-min[i];                
                    }
      
            }
//showing the array
     arrayshow(copy,r,c);
     
     
     
     
        //second table
      int min2[c];
      for(int i=0; i<c; i++){ 
          min2[i]=copy[0][i];
            for(int j=0; j<r; j++){
                   
                   if( min2[i]>copy[j][i])
                   min2[i]=copy[j][i];                
                    }
             for(int j=0; j<r; j++){
                  copy[j][i]=copy[j][i]-min2[i];                
                    }
      
            }
    
    
    //showing the array
     arrayshow(copy,r,c);
     
  int x=2*r;
          int countLines[x];
           for(int i=0; i<x; i++){
             countLines[i]=0;             
             }
     ////////////////////how many zeros at every line
                         //  for(int i=0; i<x; i++){countLines[i]=0;}
         for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                     if(copy[i][j]==0){// if(lockLines[i]!=-1){ if( lockLines[j+c]!=-1){
                         countLines[i]++;   }//}}              
                                  }    
                   // cout<<endl<<"at Row Number "<<i+1<<" There is "<<countLines[i]<<" Zeros"<<endl;
                           } 
     

     for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                    if(copy[j][i]==0){ //if(lockLines[i]!=-1){ if(lockLines[j+c]!=-1){
                         countLines[i+r]++; }//}}                
                                  } 
                   // cout<<endl<<"at column Number "<<i+1<<" There is "<<countLines[i+r]<<" Zeros"<<endl;
                            }


     
     int lock[x];
          for(int i=0; i<x; i++){
             lock[i]=0;             
             }
             
     int zeroCount=0;
     int savePlace[r];
         for(int i=0; i<x; i++){
             savePlace[i]=-99;             
                     }
                     
for(int w=1; w<c*c; w++){
     for(int i=0; i<r; i++){
            if((countLines[i]==w)&&(lock[i]!=-1)){
                   for(int j=0; j<c; j++){ 
                           if(copy[i][j]==0){
                              if(lock[j+r]!=-1){
                                 lock[i]=-1;
                                   for(int z=j+1; z<c; z++){
                                          if(copy[i][z]==0)
                                           copy[i][z]=-1000;             
                                                           }
                                     lock[j+r]=-1;
                                 
                                   for(int z=i; z<c; z++){
                                          if(copy[z][j]==0)
                                            copy[z][j]=-1000;             
                                                         }
                                 zeroCount++;
                                 savePlace[i]=j;
                                               } 
                                             }
                                          }
                                 
                                                  }            
                          }
                     }
     for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                  if(copy[i][j]==-1000)
                  copy[i][j]=0;                  
                    }
            }
            
     int lockLines[x];
     for(int i=0; i<x; i++){lockLines[i]=0;}
     
     bool lockForMax[x];
     for(int i=0; i<x; i++){lockForMax[i]=false;}
     
     int maxCountLines[x];
     for(int i=0; i<x; i++){maxCountLines[i]=0;}
     
     int savePositionLines[x];
                  for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                  if(copy[i][j]==-1000)
                  copy[i][j]=0;                  
                    }
            }
while(zeroCount!=r){
for(int i=0; i<x; i++){lockLines[i]=0;}
for(int i=0; i<x; i++){lockForMax[i]=false;}
for(int i=0; i<x; i++){maxCountLines[i]=0;}
for(int i=0; i<x; i++){savePositionLines[i]=0;}


                 //showing the array
     arrayshow(copy,r,c);
     
     

              int numberOfZeros=0;
     for(int i=0; i<r; i++){
          for(int j=0; j<c; j++){                      
                if(copy[i][j]==0)//&&lockLines[i]!=-1&&lockLines[j+c]!=-1)
                    numberOfZeros++;
                                }
                           }
                           int t=zeroCount;
while(numberOfZeros>0 ){//&& t!=0
     int www=numberOfZeros;

cout<<"DSCCADCADFW >>..>>"<<t<<endl;
                           //t--;
                           /*
        

                      
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                          /*
for(int i=0; i<x; i++){countLines[i]=0;}
         for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                     if(copy[i][j]==0){ if(lockLines[i]!=-1){ if( lockLines[j+c]!=-1){if( lockLines[i]!=-1000){if( lockLines[j+c]!=-1000){
                         countLines[i]++;   }}}}}             
                                  }    
                   // cout<<endl<<"at Row Number "<<i+1<<" There is "<<countLines[i]<<" Zeros"<<endl;
                           } 
     

     for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                    if(copy[j][i]==0){ if(lockLines[i+c]!=-1){ if(lockLines[j]!=-1){if( lockLines[i+c]!=-1000){if( lockLines[j+c]!=-1000){
                         countLines[i+r]++; }}}}}
                                  } 
                   // cout<<endl<<"at column Number "<<i+1<<" There is "<<countLines[i+r]<<" Zeros"<<endl;
                            }
    
    
    
    
    
    
    
    for(int i=0; i<x; i++){lockForMax[i]=false;}
  for(int i=0; i<x; i++){maxCountLines[i]=0;}
     for(int i=0; i<x; i++){
             for(int j=0; j<x; j++){             
              if(countLines[j]>maxCountLines[i]){ if(lockLines[i]!=-1){ if( lockLines[j]!=-1){if( lockLines[i]!=-1000){if( lockLines[j]!=-1000){
              maxCountLines[i]=countLines[j];
             int q=j;
             savePositionLines[i]= q;                  
                                                              }}}}}
                                   }
           //  lockForMax[savePositionLines[i]]=true;
           break;
                          }
                           
                     // cout<<" lockLines[savePositionLines[0]] "<<savePositionLines[0]<<endl;
                         lockLines[savePositionLines[0]]=-1;*/ 
                         
  numberOfZeros=0;
     for(int i=0; i<r; i++){
          for(int j=0; j<c; j++){                      
                 if(copy[i][j]==0){ if(lockLines[i]!=-1){ if( lockLines[j+c]!=-1){//if( lockLines[i]!=-1000){if( lockLines[j+c]!=-1000){// || (lockLines[i]!=-1 && lockLines[j+c]!=-1)) )
                    numberOfZeros++; }}}//}}
                                }
                           }
                           
                           
                           //if(numberOfZeros==www)//{t++;
                           //lockLines[savePositionLines[0]]=-1000; 
                           //}

                            }//end small while
                            
                            
                            
for(int i=0; i<x; i++){
        cout<<" line number "<<i+1<<" is "<<lockLines[i]<<endl;                                 
                           }
                            
                            
                            
 int mini;
 for(int i=0; i<r; i++){ 
         for(int j=0; j<c; j++){
                 if(lockLines[i]!=-1&&lockLines[j+c]!=-1){
                    mini=copy[i][j];        
                                                          }        
                 break;
                               }
         break;
      
                       }
 
 
 
 for(int i=0; i<r; i++){ 
         for(int j=0; j<c; j++){
                 if(lockLines[i]!=-1&&lockLines[j+c]!=-1){
                      if( mini>copy[i][j])
                      mini=copy[i][j];        
                                                          }        
                               }
            
      
                       }
                     
 cout<<"The minimum is "<<mini<<endl;
                     
                     
                  
                  
                  
 for(int i=0; i<r; i++){ 
         for(int j=0; j<c; j++){
                 if(lockLines[i]==-1&&lockLines[j+c]==-1){
                   copy[i][j]=copy[i][j]+mini;        
                                                          }        
                   else if(lockLines[i]==-1&&lockLines[j+c]!=-1){}
                   else if(lockLines[i]!=-1&&lockLines[j+c]==-1){}
                   else if(lockLines[i]!=-1&&lockLines[j+c]!=-1){
                        copy[i][j]=copy[i][j]-mini;        
                                                                }
                               }
                        }    
                  
                  
                  
      //showing the array
     arrayshow(copy,r,c);

                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    /////////////////////////////////////////
                    for(int i=0; i<x; i++){countLines[i]=0;}
         for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                     if(copy[i][j]==0){ //if(lockLines[i]!=-1){ if( lockLines[j+c]!=-1){if( lockLines[i]!=-1000){if( lockLines[j+c]!=-1000){
                         countLines[i]++;   }//}}}}             
                                  }    
                   // cout<<endl<<"at Row Number "<<i+1<<" There is "<<countLines[i]<<" Zeros"<<endl;
                           } 
     

     for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                    if(copy[j][i]==0){// if(lockLines[i]!=-1){ if(lockLines[j+c]!=-1){if( lockLines[i]!=-1000){if( lockLines[j+c]!=-1000){
                         countLines[i+r]++; }//}}}}
                                  } 
                   // cout<<endl<<"at column Number "<<i+1<<" There is "<<countLines[i+r]<<" Zeros"<<endl;
                            }
                    
                        // int lock[x];
          for(int i=0; i<x; i++){
             lock[i]=0;             
             }
             
     //int 
     zeroCount=0;
    // int savePlace[r];
         for(int i=0; i<x; i++){
             savePlace[i]=-99;             
                     }
                     
for(int w=1; w<c+1; w++){
     for(int i=0; i<r; i++){
            if(countLines[i]==w){
                                 if(lock[i]!=-1){
                   for(int j=0; j<c; j++){ 
                           if(copy[i][j]==0){
                              if(lock[j+r]!=-1){
                                 lock[i]=-1;
                                 
                                 //why if i removed them the loop stops but wrong
                                   for(int z=j; z<c; z++){
                                         if(copy[i][z]==0)
                                           copy[i][z]=-1000;             
                                                           }
                                     lock[j+r]=-1;
                                 
                                   for(int z=i; z<c; z++){
                                      if(copy[z][j]==0)
                                            copy[z][j]=-1000;             
                                                         }
                                 zeroCount++;
                                 savePlace[i]=j;
                                 cout<<"hhh "<<zeroCount<<endl;
                                               } 
                                             }
                                          }
                                 
                                                  }            
                          }
                     }}

                    
for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                  if(copy[i][j]==-1000)
                  copy[i][j]=0;                  
                    }
            }
                    
                    cout<<"zeroCount hhh .. "<<zeroCount<<endl;
                    
                    
                     }// end while(zeroCount!=r)
    
    
    
    
  //showing the array
  cout<<"hhh"<<endl;
     arrayshow(copy,r,c);

    getchar();
    getchar();
    
    return 0;
    }

#2 Bikerman

    Super Member

  • Kontributors
  • PipPipPipPipPipPipPipPipPip
  • 413 posts
  • Gender:Male
  • Location:Frodsham, Cheshire, England
  • Interests:Computing, music engineering, motorbikes, juggling
  • myCENT:6.75

Posted 19 August 2010 - 11:26 PM

There are several techniques to implement the Hungarian method algorithmically:
eg
1. Write the matrix out
Posted Image

2.Now for each row subtract the lowest value from the others in turn.
You will now have 1 or more zeros in each row - the zeros represent zero cost so you organize the tasks using the zero elements. If there are 0s in all the columns then you have your assignments. End
eg.
0...a2'..0..a4'
b1'.b2'..b3'..0
0...c2'..c3'..c4'
d1'..0..d3'..d4'

3.If the matrix does not yet have a full set of assignments then repeat for the columns (ie take the lowest value for each column). If you now have a 0 in each column then you have your assignments. End.

4. If it still does not resolve then
Repeat
a) Mark all rows which do resolve to 0
b ) Mark all columns with a 0 in that same row
c) Mark all rows with a 0 in that same column
d) Draw a line through each marked column and each unmarked row
e) Find the lowest valued unmarked element
f) Subtract that value from the marked rows
g) Add that value to the marked columns
Until all assignments (0) made.
End.

Edited by Bikerman, 19 August 2010 - 11:27 PM.

#3 Guest_Jasim_*

  • Guests

Posted 20 August 2010 - 09:53 AM

View PostBikerman, on 19 August 2010 - 11:26 PM, said:

There are several techniques to implement the Hungarian method algorithmically:
eg
1. Write the matrix out
Posted Image

2.Now for each row subtract the lowest value from the others in turn.
You will now have 1 or more zeros in each row - the zeros represent zero cost so you organize the tasks using the zero elements. If there are 0s in all the columns then you have your assignments. End
eg.
0...a2'..0..a4'
b1'.b2'..b3'..0
0...c2'..c3'..c4'
d1'..0..d3'..d4'

3.If the matrix does not yet have a full set of assignments then repeat for the columns (ie take the lowest value for each column). If you now have a 0 in each column then you have your assignments. End.

4. If it still does not resolve then
Repeat
a) Mark all rows which do resolve to 0
b ) Mark all columns with a 0 in that same row
c) Mark all rows with a 0 in that same column
d) Draw a line through each marked column and each unmarked row
e) Find the lowest valued unmarked element
f) Subtract that value from the marked rows
g) Add that value to the marked columns
Until all assignments (0) made.
End.



thank you dude

but I already know all that I have a problem implementing a)b)c)d)



I'm guessing It's unsolvable problem

#4 Bikerman

    Super Member

  • Kontributors
  • PipPipPipPipPipPipPipPipPip
  • 413 posts
  • Gender:Male
  • Location:Frodsham, Cheshire, England
  • Interests:Computing, music engineering, motorbikes, juggling
  • myCENT:6.75

Posted 20 August 2010 - 10:25 AM

Why not simply add another dimension to the array and use that as your marker/flag ? Why do you need to stick to a single dimension?
Back to C/C++ Programming · Next Unread Topic →

Reply to this topic


This post will need approval from a moderator before this post is shown.

  


1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users

  1. Discuss Anything
  2. → Main
  3. → Computers
  4. → Programming Languages
  5. → C/C++ Programming
  6. Welcome - Start here! - Free Web Hosting