172. Permutations code

לחלק מאיתנו עלה הצורך בעבר למצוא את כל התמורות של אוסף מסוים.

כלומר, למצוא את כל הסידורים האפשריים של אוסף מסוים.

לכתוב קוד כזה בד”כ דורש רקורסיה ויוצא משהו די מכוער.

בזכות מספר Featureים של השפה, ניתן לכתוב קוד כדוגמת זה בצורה יפה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(IEnumerable<T> collection)
{
if (!collection.Any())
{
// There is exactly one permutation of length 0
// the empty permutation.
yield return Enumerable.Empty<T>();
}
else
{
foreach (T firstElement in collection)
{
// firstElement will be the first element
// of our permutation.
// We now find all permutations of all
// elements except him.
IEnumerable<T> withoutCurrent =
collection.Except(new[] {firstElement});
// Get the permutations (using recursive call)
IEnumerable<IEnumerable<T>> permutationsWithoutCurrent =
GetAllPermutations(withoutCurrent);
// Iterate over the permutations of the rest elements.
foreach (IEnumerable<T> currentPermutation in permutationsWithoutCurrent)
{
// Put firstElement as the first element :)
IEnumerable<T> currentFullPermutation =
new[] {firstElement}.Concat(currentPermutation);
yield return currentFullPermutation;
}
}
}

מה שקורה כאן זה שאנחנו מקבלים אוסף ומחזירים אוסף של אוספים שמכיל את כל הסידורים האפשריים של האוסף המקורי.

איך זה עובד? כתבתי תיעוד, אבל מה שקורה זה ככה:

אם קיבלנו אוסף ריק, אנחנו מחזירים אוסף שמכיל את האוסף הריק.

אם קיבלנו אוסף אחר, אנחנו רצים על כל האיברים שלו. כל איבר כזה אנחנו מעמידים במקום הראשון באוסף ואת שאר האיברים מסדרים ברקורסיה.

שימו לב לשימוש היפה בyield return – חוץ מההתעסקות בערך ההחזר של הפונקציה, לא הייתי צריך כל הפונקציה לדעת שאני מחזיר אוסף של אוספים.

מה שעוד יפה בפונקציה זו, זה שבגלל שהיא משתמשת בyield return , אזי היא Lazy ולכן אינה מפוצצת את הזכרון בכל התמורות בקריאה אליה.

ראו גם טיפים מספר 54,55,105

שבוע טוב

שתף