none
efficient alternative to nested FOR loops

    Question

  • hi,

    i am trying make a combination of characters of length four, from two character arrays(strings) containing different set of characters.
    i did it with four nested FOR loops.
    its taking a looong time if i increase the length of the actual strings

    here's the example
    string str1 = "acdefg";
    
    string str2="qwrtyui";
    
    for(int i=0;i<str1.length;i++)
    {
          for(int j=0;i<str2.length;i++)
          {
                for(int k=0;i<str1.length;i++)
                {
                      for(int l=0;i<str1.length;i++)
                      {
                            console.WriteLine(str1[i].toString() + str1[j].toString() + str1[k].toString() + str1[l].toString() + "\n");
    
                      }
                }
          }
    }
    can this be improved into a better algo?


    My nephew says: "Mathematics and Politics are a part of life."
    Tuesday, June 23, 2009 12:56 PM

Answers

  • not really
    Mark the best replies as answers. "Fooling computers since 1971."
    • Proposed as answer by Matthew Watson Tuesday, June 23, 2009 2:47 PM
    • Marked as answer by Bin-ze Zhao Monday, June 29, 2009 8:10 AM
    Tuesday, June 23, 2009 1:16 PM
  • Derar friends thanks a lot for your time.
    I solved my problem is now solved.
    it took 00:00:00.4568767 seconds
    to generate 157464 items and saved them to a text file.


    actually i was using winforms + appending the output to the RTF control!


    Thanks

    My nephew says: "Mathematics and Politics are a part of life."
    • Marked as answer by Bin-ze Zhao Monday, June 29, 2009 8:10 AM
    Tuesday, June 23, 2009 2:21 PM

All replies

  • Not really.
    Mark the best replies as answers. "Fooling computers since 1971."
    Tuesday, June 23, 2009 1:00 PM
  • i am running four nested loops for More than 12 hours, i have a PC with a 2.8 HT processor and 1G of Memory.!!!!
    the strings are 26 and 8 characters long.

    My nephew says: "Mathematics and Politics are a part of life."
    • Edited by Jey Keu Tuesday, June 23, 2009 1:04 PM
    Tuesday, June 23, 2009 1:04 PM
  • By the way... what's probably making your code take a loooong time, is the Console.WriteLine. Do you really want to display them all?

    Anyways, your algorithm will always be O(m2 n2 ).

    I always try to Keep it Sharp & simple.
    Tuesday, June 23, 2009 1:06 PM
  • lol... now I see it.

    You are always comparing and increasing the variable i in the fors.

    for(int k=0;i <str1.length;i ++)


    I always try to Keep it Sharp & simple.
    Tuesday, June 23, 2009 1:09 PM
  • suppose there is no error in the code. please suggest based on the nested loops.
    My nephew says: "Mathematics and Politics are a part of life."
    Tuesday, June 23, 2009 1:10 PM
  • I think you typed in that code rather hastily.  It doesn't make much sense and there are numerous problems.  You're not incrementing the correct loop variable (I see a lot of i++ but no j++ , k++ or l++ ), it doesn't look like you're looking at the right string's length (I see str1.length three times, but str2.length only once), and you aren't taking characters from the right string (I see str1[x] , but never str2[x] )  and you don't need to append "\n" if you're using WriteLine.

    Why do you have two strings?  I'm a little unclear on what you are trying to do.  Can you give some examples of the kinds of strings you want to generate?

    You said they are combinations of characters of length 4.  So your final string is 4 characters long.  But you are taking characters from two strings?  I just don't get why are there two strings?

    For example, my instinct is to do this (in pseudo-code)
    str3 = str1 + str2;
    for( int i=0; i<4; i++ ) {
       n = random number between 0 and str3.length - 1;
       output.append( str3[ n ] );
    }

    So, what are you really trying to do?
    Tuesday, June 23, 2009 1:12 PM
  • please consider nested loops concept and  the length of the two strings being processed.
    and suppose that the above code works fine without errors. is there a better ways to do that??

    My nephew says: "Mathematics and Politics are a part of life."
    Tuesday, June 23, 2009 1:14 PM
  • not really
    Mark the best replies as answers. "Fooling computers since 1971."
    • Proposed as answer by Matthew Watson Tuesday, June 23, 2009 2:47 PM
    • Marked as answer by Bin-ze Zhao Monday, June 29, 2009 8:10 AM
    Tuesday, June 23, 2009 1:16 PM
  • here's the example of combinations that can be generated

    string str1 = "acdefg";
    
    string str2="qwrtyui";

    aqac
    
    aqcd
    
    awac
    
    awcd
    
    cqac
    
    cqcd
    
    cwac
    
    cwcd




    My nephew says: "Mathematics and Politics are a part of life."
    Tuesday, June 23, 2009 1:20 PM
  • No, there is no better way. As rudedog eloquently said it.

    By the way, there probably is an error in your code:

    Stopwatch sw = new Stopwatch();
    sw.Start();
    List<string> list = new List<string>();
    string str1 = "abcdefghijklmnopqrstuvwxyz";
    string str2 = "01234567";
    
    for (int i = 0; i < str1.Length; i++)
    {
        for (int j = 0; j < str2.Length; j++)
        {
            for (int k = 0; k < str1.Length; k++)
            {
                for (int l = 0; l < str2.Length; l++)
                {
                    list.Add(str1[i].ToString() + str2[j].ToString() + str1[k].ToString() + str2[l].ToString());
                    Console.WriteLine(str1[i].ToString() + str2[j].ToString() + str1[k].ToString() + str2[l].ToString());
                }
            }
        }
    }
    sw.Stop();
    Console.WriteLine(sw.Elapsed);
    

    This ran on my PC in less than a minute in debug mode, and in less than 0.07 seconds with the WriteLine commented.

    I always try to Keep it Sharp & simple.
    Tuesday, June 23, 2009 1:20 PM
  • OK, changed the combination to be str1, 2, 1, 1 as you stated above. Still less than 3 minutes debugging . I'm to lazy to create a new Console Application and test it in release :P
    I always try to Keep it Sharp & simple.
    Tuesday, June 23, 2009 1:27 PM
  • no, just save the output. i tried the code w/o CW, it executed fast.
    My nephew says: "Mathematics and Politics are a part of life."
    Tuesday, June 23, 2009 1:28 PM
  • its mistyped here,
    assume the code has no errors

    My nephew says: "Mathematics and Politics are a part of life."
    Tuesday, June 23, 2009 1:29 PM
  • Think of it like numbers.  Suppose you wanted to print out all of the four-digit numbers where each digit is a number between 0 and 9. 

    There are 10 * 10 * 10 * 10 = 10000 of them.  Ranging from 0000 to 9999

    You could print them all out like this:

    for( int a=0; a<=9; a++ ) {
       for( int b=0; b<=9; b++ ) {
          for( int c=0; c<=9; c++ ) {
             for( int d=0; d<=9; d++ ) {
                Console.WriteLine( "{0}{1}{2}{3}", a, b, c, d );
             }
          }
       }
    }
    
    But if you use all the letters from A -> Z as your digits then, you get 26 * 26 * 26 * 26 = 456976 results.

    This still shouldn't take 12 hours, even if you display them all.  on my machine, I can print half a million WriteLines in about 10 seconds.

    But even if you used all letters and all digits, that's 36 * 36 * 36 * 36 and it still only takes about 35 seconds to print them all on my machine.

    Something is wrong with your code.
    Tuesday, June 23, 2009 1:33 PM
  • How about cutting and pasting your actual code here so we can see the real problem?
    Tuesday, June 23, 2009 1:36 PM
  • Derar friends thanks a lot for your time.
    I solved my problem is now solved.
    it took 00:00:00.4568767 seconds
    to generate 157464 items and saved them to a text file.


    actually i was using winforms + appending the output to the RTF control!


    Thanks

    My nephew says: "Mathematics and Politics are a part of life."
    • Marked as answer by Bin-ze Zhao Monday, June 29, 2009 8:10 AM
    Tuesday, June 23, 2009 2:21 PM