שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2023 - מיון

נתונה הבעיה האלגוריתמית הבאה: הקלט הוא $m$ מערכים בגודל $k$ כל אחד, כאשר כל אחד מ-$m$ המערכים מכיל תמורה של $1,\ldots,k$. הפלט הוא $m$ המערכים כשכל אחד מהם ממוין. מה מספר הקלטים האפשריים לבעיה?

רמז: כל מערך הוא תמורה של $\{1,\ldots,k\}$ באופן בלתי תלוי. כמה תמורות יש לכל מערך, וכמה מערכים יש?

פתרון: כל אחד מ-$m$ המערכים מכיל תמורה של $\{1, 2, \ldots, k\}$. מספר התמורות האפשריות לכל מערך הוא $k!$. מכיוון שיש $m$ מערכים בלתי תלויים זה מזה, מספר הקלטים האפשריים הוא: $$(k!)^m$$