מריה בוטוסוב

יש למצוא את כל הפרמוטציות (חילוף) של מחרוזת נתונה.

public void permutation(string str, string prefix)
{
    if(str.Length==0)  {
        Console.WriteLine(prefix);
    }
    else {
        for (int i = 0; i< str.Length; i++) {
            string rem = str.Substring(0, i) + str.Substring(i + 1);
            permutation(rem, prefix + str[i]); 
        }
    }
}

הסבר:

זמן ריצה:

אלגוריטם לא עושה דבר מלבד להחזיק תו אחד קבוע ואז לחשב את הפרמוטציות של האחרים.

                           +---+
    +----------------------+GOD+--------------------+
    |                      +---+                    |
    |Swap G with G           |Swap G with O         | Swap G with D
    |                        |                      |
    |                        |                      |
  +-v-+                    +-v-+                  +-v-+
  |GOD|                    |OGD|                  |DOG|
  +---+G is fixed          +---+O is fixed        +---+D is fixed
    |                        |                      |
    |Swap O with D           |Swap G with D         |Swap O with G
    |                        |                      |
  +-v-+                    +-v-+                  +-v-+
  |GDO|                    |ODG|                  |DGO|
  +---+G and D is fixed    +---+O and D is fixed  +---+D and G is fixed