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

[iGuest 3]

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 unbalancedif(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;    }

[Bikerman 2]

There are several techniques to implement the Hungarian method algorithmically:

eg

1. Write the matrix out

 

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 August 19, 2010 by Bikerman (see edit history)

[iGuest 3]

There are several techniques to implement the Hungarian method algorithmically:

eg

1. Write the matrix out

 

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

[Bikerman 2]

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?