Solved

C# string permutation

Posted on 2011-09-13
6
1,418 Views
Last Modified: 2012-05-12
string permutation  , not able understand.
using System;
using System.Text;

namespace Permutations
{
        class Permute
        {
                 private void swap (ref char a,ref char b)
                 {
                        if(a==b)return;
                        a^=b;
                        b^=a;
                        a^=b;
                  }

                  public void Set_Permutation(char[] list)
                  {
                        int arrayLength=list.Length-1;
                        Permutation_Method(list,0,arrayLength);
                  }

                  private void Permutation_Method (char[] list,int k,int m)
                  {
                      // k intial index passed 
                      // m size of char array
                        int i;
                        if(k == m)  // ---------- What is this Condition ?
                           {
                                 Console.Write(list);
                                 Console.WriteLine(" ");
                            }
                        else
                             for(i = k; i <= m; i++) //  why i=k ?
                            {
                                   swap(ref list[k], ref list[i]);  // what does this Swap doing ?

                                    //recursive call
                                   Permutation_Method (list, k+1, m);

                                   swap(ref list[k], ref list[i]);   // what does this Swap doing ?
                            }
                   }
         }

         class Class1
        {
               static void Main()
               {

                      Permute objPermutation =new Permute();
                      string str="abc";
                       char[] mycharArray=str.ToCharArray();
                       /*calling the permute*/
                      objPermutation.Set_Permutation(mycharArray);
                  }
           }

}

Open in new window


Can some one explain what exactly happening  for  above code  where I marked questions

     
0
Comment
Question by:N_Sri
  • 3
  • 2
6 Comments
 
LVL 9

Accepted Solution

by:
oheil earned 250 total points
ID: 36534422
if(k == m)  // ---------- What is this Condition ?

This is the end of the recursion.
Method Permutation_Method calls itself so there must be a end of recursion condition. If it would not be there, the result would be an endless call (not endless but until stack overflow fatal error).

for(i = k; i <= m; i++) //  why i=k ?
The start of the recursion call (first call to Permutation_Method) is with k = 0, which means, start with the first character in the string (array of characters).
Than swap the two characters at position k and i (which does nothing at the first call).
Next call with k=1.
Again k = i, nothing ist done in the first m rounds of recursion.
When they are ready, condition k = m, than another round starts, now with k always k = i + 1, and than
always character at positon i and k = i + 1 and in the new call of Permutation_Method with k + 1, swapping
character i and k+2, and so on.
Result is some kind of permutaion of all characters in the string. The exact permutation is not easy
to oversee for me without debugging the code, so I would insert Console.Write(list); at before and after

Permutation_Method (list, k+1, m);

just to see how list evolves.

Hope it helps,

Oli




0
 
LVL 7

Assisted Solution

by:Slimfinger
Slimfinger earned 100 total points
ID: 36534494
The function Set_Permutation() displays all permutations of the array of characters passed to it.

To answer your questions:

if (k == m)  // ---------- What is this Condition ?
this checks if the given index 'k' is the last index to be checked.

swap(ref list[k], ref list[ii]);  // what does this Swap doing ?
this swaps the values of the two given characters.

Though at first glance the function seems to work (in that it properly displays all the character permutations), the code is a bit misleading:
a) the variable 'arrayLength' is not the array length, but the index of the final element.  Similarly, the variable 'm' is notated as "size of the array" when it is not.
b) Set_Permutation doesn't set a permutation, but simply results in displaying all permutations.

Simply renaming some var's and functions ('arrayLength' --> 'indexLast' and 'Set_Permutation' --> 'DisplayPermutations') would make it clearer.
0
 

Assisted Solution

by:N_Sri
N_Sri earned 0 total points
ID: 36534532
Thankyou, oheil:

I still did not understand the logic, can you explain out line of program logic in simple words.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 9

Expert Comment

by:oheil
ID: 36535077
I'll try:

The magic word is "recursion", I asume that you have problems with this concept.

A function calls itself with new parameters as long as the end condition is reached.

This is a very simple example, the famous fibunacci numbers:

1, 1, 2, 3, 5, 8, 13, 21, .

each fibunacci number ist the sum of the two numbers before.

The recursive program would be (in some syntax):

int fib(int a) {
  if (a==1 OR a==2) return 1;   //end of recursion condition
  else return fib(a-1)+fib(a-2);   //recursive calls of it self (two times)
}

calling fib(4) gives the fourth fibunacci number, because
fib(4)  calls  fib(3)+fib(2)
fib(2) returns 1 because of the "end-of-recursion"-condition
fib(3) calls fib(2)+fib(1)
again fib(2) returns 1 and fib(1) also, therefore calling fib(3) returns 1+1=2
now fib(4) returns with 2+1=3
result is 3.

This is the calling stack:

fib(4)
  -> fib(3)      and     -> fib(2)
      -> fib(2)                    returns 1
           returns 1

Hope this helps and the assumption that recursion is the problem is true :-)

If not i'll try again.

Oli





0
 

Author Comment

by:N_Sri
ID: 36538085
So how it will be for
// please write some pseudo code

Permutation( ABCD)=
0
 

Author Closing Comment

by:N_Sri
ID: 36558837
thankyou
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Why don't I see this table in EDMX file? 2 23
Error on link 14 37
Reset asp.net login password 4 29
C#.NET and microsoft certification. 3 31
Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
This article aims to explain the working of CircularLogArchiver. This tool was designed to solve the buildup of log file in cases where systems do not support circular logging or where circular logging is not enabled
Internet Business Fax to Email Made Easy - With  eFax Corporate (http://www.enterprise.efax.com), you'll receive a dedicated online fax number, which is used the same way as a typical analog fax number. You'll receive secure faxes in your email, f…
Learn how to create flexible layouts using relative units in CSS.  New relative units added in CSS3 include vw(viewports width), vh(viewports height), vmin(minimum of viewports height and width), and vmax (maximum of viewports height and width).

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now