473,324 Members | 2,178 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

how can i get every possible answer with one dimension array(brute force)

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
Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. //#include<cstdlib>
  3. //#include"time.h"
  4.  
  5. using namespace std;
  6.  
  7. void arrayshow(int a[5][5], int r, int c)
  8. {
  9.          //showing the array
  10.     cout<<"your table is"<<endl;
  11.     cout<<"\t\t";
  12.     for(int j=0; j<c; j++){
  13.             cout<<"Y"<<j+1<<"\t";        
  14.                           }
  15. cout<<endl<<endl;
  16.     for(int i=0; i<r; i++){
  17.             cout<<"        X"<<i+1<<"\t";
  18.          for(int j=0; j<c; j++){
  19.                  cout<<a[i][j]<<"\t";
  20.                                }
  21.          cout<<endl;
  22.                           }
  23. }
  24.  
  25.  
  26. int main(){
  27.  
  28.      int r=5;
  29.     int c=5;
  30.     /*
  31.     cout<<"enter rows number"<<endl;
  32.     cin>>r;
  33.  
  34.     cout<<"enter columns number"<<endl;
  35.     cin>>c;
  36.  
  37.     //initiating the array
  38.     int a[100][100];
  39.         for(int i=0; i<100; i++){
  40.             for(int j=0; j<100; j++){
  41.                     a[i][j]=0;                  
  42.                     }
  43.  
  44.             }
  45.     //filling the array
  46.     cout<<"enter costs"<<endl;
  47.  
  48.     for(int i=0; i<r; i++){
  49.            for(int j=0; j<c; j++){
  50.                   cout<<"enter X"<<i+1<<"Y"<<j+1<<"   ";
  51.                    cin>>a[i][j];
  52.  
  53.                    }
  54.  
  55.          }
  56.       */
  57.   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};
  58.             //showing the array
  59.             arrayshow(a,r,c);
  60.  
  61.  
  62.        /*     
  63.  
  64.     cout<<"your table is"<<endl;
  65.     cout<<"\t\t";
  66.                 for(int j=0; j<c; j++){
  67.                     cout<<"Y"<<j+1<<"\t";
  68.  
  69.                     }
  70.     cout<<endl<<endl;
  71.         for(int i=0; i<r; i++){
  72.                 cout<<"        X"<<i+1<<"\t";
  73.             for(int j=0; j<c; j++){
  74.                     cout<<a[i][j]<<"\t";
  75.  
  76.                     }
  77.             cout<<endl;
  78.             }*/
  79.  
  80.  
  81.  
  82.  
  83.  
  84.     //checking for unbalanced
  85. if(c<r){
  86.         int y=r-c;  
  87.         c=c+y;
  88.         }
  89.  
  90.  
  91. if(c>r){
  92.         int y=c-r;
  93.         r=r+y;
  94.         }
  95.  
  96.  
  97.  
  98.  
  99.  
  100.     //showing the array
  101.     arrayshow(a,r,c);
  102.  
  103.     //coping the array
  104.     int copy[5][5];
  105.  
  106.     for(int i=0; i<r; i++){
  107.             for(int j=0; j<c; j++){
  108.                   copy[i][j]=a[i][j];                  
  109.                     }
  110.             }
  111.  
  112.         //showing the array
  113.     cout<<"THE COPIED TABLE IS"<<endl;
  114.    arrayshow(copy,r,c);
  115.  
  116.  
  117.  
  118.  // min or max
  119.     int choice;
  120.     cout<<"please type your choice:     "<<endl;
  121.     cout<<"1- minimization.."<<endl;
  122.     cout<<"2- maximization.."<<endl;
  123.     cin>>choice;
  124.  
  125.     if (choice==2){
  126.        int max=0;
  127.  
  128.        for(int i=0; i<r; i++){
  129.             for(int j=0; j<c; j++){
  130.                   if(max<copy[i][j])
  131.                   max=copy[i][j];                  
  132.                     }
  133.             } 
  134.  
  135.  
  136.        for(int i=0; i<r; i++){
  137.             for(int j=0; j<c; j++){
  138.                     copy[i][j]=max-copy[i][j];                  
  139.                     }
  140.             } 
  141.        //showing the array
  142.     cout<<"maximization after fixing"<<endl;
  143.    arrayshow(copy,r,c);      
  144.                    } 
  145.  
  146.  
  147.  
  148.    //first table
  149.       int min[r];
  150.       for(int i=0; i<r; i++){ 
  151.           min[i]=copy[i][0];
  152.             for(int j=0; j<c; j++){
  153.  
  154.                    if( min[i]>copy[i][j])
  155.                    min[i]=copy[i][j];                
  156.                     }
  157.              for(int j=0; j<c; j++){
  158.                   copy[i][j]=copy[i][j]-min[i];                
  159.                     }
  160.  
  161.             }
  162. //showing the array
  163.      arrayshow(copy,r,c);
  164.  
  165.  
  166.  
  167.  
  168.         //second table
  169.       int min2[c];
  170.       for(int i=0; i<c; i++){ 
  171.           min2[i]=copy[0][i];
  172.             for(int j=0; j<r; j++){
  173.  
  174.                    if( min2[i]>copy[j][i])
  175.                    min2[i]=copy[j][i];                
  176.                     }
  177.              for(int j=0; j<r; j++){
  178.                   copy[j][i]=copy[j][i]-min2[i];                
  179.                     }
  180.  
  181.             }
  182.  
  183.  
  184.     //showing the array
  185.      arrayshow(copy,r,c);
  186.  
  187.   int x=2*r;
  188.           int countLines[x];
  189.            for(int i=0; i<x; i++){
  190.              countLines[i]=0;             
  191.              }
  192.      ////////////////////how many zeros at every line
  193.                          //  for(int i=0; i<x; i++){countLines[i]=0;}
  194.          for(int i=0; i<r; i++){
  195.             for(int j=0; j<c; j++){
  196.                      if(copy[i][j]==0){// if(lockLines[i]!=-1){ if( lockLines[j+c]!=-1){
  197.                          countLines[i]++;   }//}}              
  198.                                   }    
  199.                    // cout<<endl<<"at Row Number "<<i+1<<" There is "<<countLines[i]<<" Zeros"<<endl;
  200.                            } 
  201.  
  202.  
  203.      for(int i=0; i<r; i++){
  204.             for(int j=0; j<c; j++){
  205.                     if(copy[j][i]==0){ //if(lockLines[i]!=-1){ if(lockLines[j+c]!=-1){
  206.                          countLines[i+r]++; }//}}                
  207.                                   } 
  208.                    // cout<<endl<<"at column Number "<<i+1<<" There is "<<countLines[i+r]<<" Zeros"<<endl;
  209.                             }
  210.  
  211.  
  212.  
  213.      int lock[x];
  214.           for(int i=0; i<x; i++){
  215.              lock[i]=0;             
  216.              }
  217.  
  218.      int zeroCount=0;
  219.      int savePlace[r];
  220.          for(int i=0; i<x; i++){
  221.              savePlace[i]=-99;             
  222.                      }
  223.  
  224. for(int w=1; w<c*c; w++){
  225.      for(int i=0; i<r; i++){
  226.             if((countLines[i]==w)&&(lock[i]!=-1)){
  227.                    for(int j=0; j<c; j++){ 
  228.                            if(copy[i][j]==0){
  229.                               if(lock[j+r]!=-1){
  230.                                  lock[i]=-1;
  231.                                    for(int z=j+1; z<c; z++){
  232.                                           if(copy[i][z]==0)
  233.                                            copy[i][z]=-1000;             
  234.                                                            }
  235.                                      lock[j+r]=-1;
  236.  
  237.                                    for(int z=i; z<c; z++){
  238.                                           if(copy[z][j]==0)
  239.                                             copy[z][j]=-1000;             
  240.                                                          }
  241.                                  zeroCount++;
  242.                                  savePlace[i]=j;
  243.                                                } 
  244.                                              }
  245.                                           }
  246.  
  247.                                                   }            
  248.                           }
  249.                      }
  250.      for(int i=0; i<r; i++){
  251.             for(int j=0; j<c; j++){
  252.                   if(copy[i][j]==-1000)
  253.                   copy[i][j]=0;                  
  254.                     }
  255.             }
  256.  
  257.      int lockLines[x];
  258.      for(int i=0; i<x; i++){lockLines[i]=0;}
  259.  
  260.      bool lockForMax[x];
  261.      for(int i=0; i<x; i++){lockForMax[i]=false;}
  262.  
  263.      int maxCountLines[x];
  264.      for(int i=0; i<x; i++){maxCountLines[i]=0;}
  265.  
  266.      int savePositionLines[x];
  267.                   for(int i=0; i<r; i++){
  268.             for(int j=0; j<c; j++){
  269.                   if(copy[i][j]==-1000)
  270.                   copy[i][j]=0;                  
  271.                     }
  272.             }
  273. while(zeroCount!=r){
  274. for(int i=0; i<x; i++){lockLines[i]=0;}
  275. for(int i=0; i<x; i++){lockForMax[i]=false;}
  276. for(int i=0; i<x; i++){maxCountLines[i]=0;}
  277. for(int i=0; i<x; i++){savePositionLines[i]=0;}
  278.  
  279.  
  280.                  //showing the array
  281.      arrayshow(copy,r,c);
  282.  
  283.  
  284.  
  285.               int numberOfZeros=0;
  286.      for(int i=0; i<r; i++){
  287.           for(int j=0; j<c; j++){                      
  288.                 if(copy[i][j]==0)//&&lockLines[i]!=-1&&lockLines[j+c]!=-1)
  289.                     numberOfZeros++;
  290.                                 }
  291.                            }
  292.                            int t=zeroCount;
  293.                            ///why is this loop  infinite
  294. while(numberOfZeros>0 ){//&& t!=0
  295.      int www=numberOfZeros;
  296.  
  297. cout<<"DSCCADCADFW >>..>>"<<t<<endl;
  298.                            //t--;
  299.                            /*
  300.                  int rndm[numberOfZeros];
  301.                  for(int i=0; i<numberOfZeros; i++){rndm[i]=-1000;}
  302.  
  303.  
  304.  
  305.                  for(int i=0; i<numberOfZeros; i++){
  306.  
  307.                          srand(time(NULL)); 
  308.                          rndm[i]=rand();
  309.                          rndm[i]=rndm[i]%numberOfZeros;
  310.                          for(int j=0; j<numberOfZeros; j++){
  311.                                  if(i!=j){
  312.                                  if(rndm[i]==rndm[j]){rndm[i]=-1000;i--;}
  313.                                  }
  314.                                  }                         
  315.  
  316.  
  317.                          }          
  318.  
  319.  
  320.  
  321.                            for(int i=0; i<numberOfZeros; i++){lockLines[rndm[i]];}
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.                           /*
  339. for(int i=0; i<x; i++){countLines[i]=0;}
  340.          for(int i=0; i<r; i++){
  341.             for(int j=0; j<c; j++){
  342.                      if(copy[i][j]==0){ if(lockLines[i]!=-1){ if( lockLines[j+c]!=-1){if( lockLines[i]!=-1000){if( lockLines[j+c]!=-1000){
  343.                          countLines[i]++;   }}}}}             
  344.                                   }    
  345.                    // cout<<endl<<"at Row Number "<<i+1<<" There is "<<countLines[i]<<" Zeros"<<endl;
  346.                            } 
  347.  
  348.  
  349.      for(int i=0; i<r; i++){
  350.             for(int j=0; j<c; j++){
  351.                     if(copy[j][i]==0){ if(lockLines[i+c]!=-1){ if(lockLines[j]!=-1){if( lockLines[i+c]!=-1000){if( lockLines[j+c]!=-1000){
  352.                          countLines[i+r]++; }}}}}
  353.                                   } 
  354.                    // cout<<endl<<"at column Number "<<i+1<<" There is "<<countLines[i+r]<<" Zeros"<<endl;
  355.                             }
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.     for(int i=0; i<x; i++){lockForMax[i]=false;}
  364.   for(int i=0; i<x; i++){maxCountLines[i]=0;}
  365.      for(int i=0; i<x; i++){
  366.              for(int j=0; j<x; j++){             
  367.               if(countLines[j]>maxCountLines[i]){ if(lockLines[i]!=-1){ if( lockLines[j]!=-1){if( lockLines[i]!=-1000){if( lockLines[j]!=-1000){
  368.               maxCountLines[i]=countLines[j];
  369.              int q=j;
  370.              savePositionLines[i]= q;                  
  371.                                                               }}}}}
  372.                                    }
  373.            //  lockForMax[savePositionLines[i]]=true;
  374.            break;
  375.                           }
  376.  
  377.                      // cout<<" lockLines[savePositionLines[0]] "<<savePositionLines[0]<<endl;
  378.                          lockLines[savePositionLines[0]]=-1;*/ 
  379.  
  380.   numberOfZeros=0;
  381.      for(int i=0; i<r; i++){
  382.           for(int j=0; j<c; j++){                      
  383.                  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)) )
  384.                     numberOfZeros++; }}}//}}
  385.                                 }
  386.                            }
  387.  
  388.  
  389.                            //if(numberOfZeros==www)//{t++;
  390.                            //lockLines[savePositionLines[0]]=-1000; 
  391.                            //}
  392.  
  393.                             }//end small while
  394.  
  395.  
  396.  
  397. for(int i=0; i<x; i++){
  398.         cout<<" line number "<<i+1<<" is "<<lockLines[i]<<endl;                                 
  399.                            }
  400.  
  401.  
  402.  
  403.  int mini;
  404.  for(int i=0; i<r; i++){ 
  405.          for(int j=0; j<c; j++){
  406.                  if(lockLines[i]!=-1&&lockLines[j+c]!=-1){
  407.                     mini=copy[i][j];        
  408.                                                           }        
  409.                  break;
  410.                                }
  411.          break;
  412.  
  413.                        }
  414.  
  415.  
  416.  
  417.  for(int i=0; i<r; i++){ 
  418.          for(int j=0; j<c; j++){
  419.                  if(lockLines[i]!=-1&&lockLines[j+c]!=-1){
  420.                       if( mini>copy[i][j])
  421.                       mini=copy[i][j];        
  422.                                                           }        
  423.                                }
  424.  
  425.  
  426.                        }
  427.  
  428.  cout<<"The minimum is "<<mini<<endl;
  429.  
  430.  
  431.  
  432.  
  433.  
  434.  for(int i=0; i<r; i++){ 
  435.          for(int j=0; j<c; j++){
  436.                  if(lockLines[i]==-1&&lockLines[j+c]==-1){
  437.                    copy[i][j]=copy[i][j]+mini;        
  438.                                                           }        
  439.                    else if(lockLines[i]==-1&&lockLines[j+c]!=-1){}
  440.                    else if(lockLines[i]!=-1&&lockLines[j+c]==-1){}
  441.                    else if(lockLines[i]!=-1&&lockLines[j+c]!=-1){
  442.                         copy[i][j]=copy[i][j]-mini;        
  443.                                                                 }
  444.                                }
  445.                         }    
  446.  
  447.  
  448.  
  449.       //showing the array
  450.      arrayshow(copy,r,c);
  451.  
  452.  
  453.  
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.                     /////////////////////////////////////////
  482.                     for(int i=0; i<x; i++){countLines[i]=0;}
  483.          for(int i=0; i<r; i++){
  484.             for(int j=0; j<c; j++){
  485.                      if(copy[i][j]==0){ //if(lockLines[i]!=-1){ if( lockLines[j+c]!=-1){if( lockLines[i]!=-1000){if( lockLines[j+c]!=-1000){
  486.                          countLines[i]++;   }//}}}}             
  487.                                   }    
  488.                    // cout<<endl<<"at Row Number "<<i+1<<" There is "<<countLines[i]<<" Zeros"<<endl;
  489.                            } 
  490.  
  491.  
  492.      for(int i=0; i<r; i++){
  493.             for(int j=0; j<c; j++){
  494.                     if(copy[j][i]==0){// if(lockLines[i]!=-1){ if(lockLines[j+c]!=-1){if( lockLines[i]!=-1000){if( lockLines[j+c]!=-1000){
  495.                          countLines[i+r]++; }//}}}}
  496.                                   } 
  497.                    // cout<<endl<<"at column Number "<<i+1<<" There is "<<countLines[i+r]<<" Zeros"<<endl;
  498.                             }
  499.  
  500.                         // int lock[x];
  501.           for(int i=0; i<x; i++){
  502.              lock[i]=0;             
  503.              }
  504.  
  505.      //int 
  506.      zeroCount=0;
  507.     // int savePlace[r];
  508.          for(int i=0; i<x; i++){
  509.              savePlace[i]=-99;             
  510.                      }
  511.  
  512. for(int w=1; w<c+1; w++){
  513.      for(int i=0; i<r; i++){
  514.             if(countLines[i]==w){
  515.                                  if(lock[i]!=-1){
  516.                    for(int j=0; j<c; j++){ 
  517.                            if(copy[i][j]==0){
  518.                               if(lock[j+r]!=-1){
  519.                                  lock[i]=-1;
  520.  
  521.                                  //why if i removed them the loop stops but wrong
  522.                                    for(int z=j; z<c; z++){
  523.                                          if(copy[i][z]==0)
  524.                                            copy[i][z]=-1000;             
  525.                                                            }
  526.                                      lock[j+r]=-1;
  527.  
  528.                                    for(int z=i; z<c; z++){
  529.                                       if(copy[z][j]==0)
  530.                                             copy[z][j]=-1000;             
  531.                                                          }
  532.                                  zeroCount++;
  533.                                  savePlace[i]=j;
  534.                                  cout<<"hhh "<<zeroCount<<endl;
  535.                                                } 
  536.                                              }
  537.                                           }
  538.  
  539.                                                   }            
  540.                           }
  541.                      }}
  542.  
  543.  
  544. for(int i=0; i<r; i++){
  545.             for(int j=0; j<c; j++){
  546.                   if(copy[i][j]==-1000)
  547.                   copy[i][j]=0;                  
  548.                     }
  549.             }
  550.  
  551.                     cout<<"zeroCount hhh .. "<<zeroCount<<endl;
  552.  
  553.  
  554.                      }// end while(zeroCount!=r)
  555.  
  556.  
  557.  
  558.  
  559.   //showing the array
  560.   cout<<"hhh"<<endl;
  561.      arrayshow(copy,r,c);
  562.  
  563.  
  564.  
  565.  
  566.  
  567.  
  568.  
  569.  
  570.  
  571.  
  572.  
  573.  
  574.  
  575.  
  576.  
  577.  
  578.  
  579.  
  580.  
  581.  
  582.  
  583.  
  584.  
  585.  
  586.  
  587.  
  588.  
  589.  
  590.  
  591.  
  592.  
  593.  
  594.  
  595.     getchar();
  596.     getchar();
  597.  
  598.     return 0;
  599.     }
  600.  

please help me there is only a week for my dead line



sorry about my English
Aug 18 '10 #1
2 1124
donbock
2,426 Expert 2GB
You mention two tasks: find all "i choose j" combinations (look here); and implement the Hungarian algorithm (to solve the assignment problem). Which do you want help with?
Aug 18 '10 #2
Stewart Ross
2,545 Expert Mod 2GB
I have closed this thread which is a repost of a homework question. The previous post was deleted and the poster advised to read our guidelines accordingly.

MODERATOR
Aug 18 '10 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
by: ago | last post by:
Inspired by some recent readings on LinuxJournal and an ASPN recipe, I decided to revamp my old python hack... The new code is a combination of (2) reduction methods and brute force and it is quite...
3
by: Captain Dondo | last post by:
First of all, thanks for the serialize pointer in an earlier thread. That looks like it's the ticket. Now, I have a style/php question. (I am a C hacker by background, and thus everything is a...
0
by: scoe | last post by:
In designing a application to update firmware, I require to reset the hardware. Is their any command or method to force a reset of the device.
6
by: Hubert Fritz | last post by:
Hello, I fear I want to have something which is not possible in C++. How is it possible to define a base class so that the derived class is forced to contain a static member variable, which...
11
by: estantep | last post by:
Hello, I am trying to find out an alternate way to brute-force a variable length vector with different variable length contents. int chromossome int max_value_for_each_chromossome
38
by: Boon | last post by:
Hello group, I've been toying with a simple sudoku solver. I meant for the code to be short and easy to understand. I figured "brute force is simple" -- who needs finesse, when you've got...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.