האם הדרך היעילה ביותר לבחור X פריטים מרשימה באופן רנדומלי מבלי כפילויות היא ליצור העתק של הרשימה, לעבור בלולאה X פעמים, ליצור משתנה רנדומלי חדש בטווח i עד מספר הפריטים ברשימה, ולמחוק את החוליה מהרשימה כך שלא תיבחר שוב?

דוגמה (C#):

קוד PHP:

 //המערך שאליו יכנסו הפריטים שנבחרו באקראי
a = new int[wrdcnt];
 

            int randomum;
//העתק של הרשימה על מנת לא לפגוע ברשימה המקורית
        List<int> l2 = new List<int> (l1);

            for (int i = 0; i < a.Length; i++)
            {

                randomum = r1.Next(i, l2.Count);


                a[i] = int.Parse(l2[randomum].ToString());
                l2.RemoveAt(randomum);

            } 


Ramboli

נניח כי בוחרים [tex]k[/tex] איברים מתוך [tex]n[/tex] איברים.
האלגוריתם שלך לוקח זמן של [tex]\Theta(nk)[/tex] במקרה הממוצע, כי הסרה ממוצעת מרשימה לוקחת [tex]\Theta(n)[/tex].
יש לי שני רעיונות שאחד מהם לוקח [tex]\Theta(k\cdot\log k)[/tex] והשני [tex]\Theta(n)[/tex] (במקרה הגרוע) כך שאיזה טוב יותר תלוי ב-[tex]k[/tex]. לגלות או שאתה מעדיף את זה כחידה?
אגב, מה ההסבר שלך לשורה:

קוד:

a[i] = int.Parse(l2[randomum].ToString());

לא חבל להמיר למחרוזת ובחזרה?

תודה על התגובה,
הידע שלי במתמטיקה הוא של 5 יחידות בתיכון ולא מעבר לזה..

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

תיקנתי את השורה :

קוד PHP:

 a[i] =l2[randomum]; 


ד"א הייתה לי שגיאה בקוד, הטווח של המספר הרנדומלי צריך להיות תמיד מ-0 כי אני מעדכן את הרשימה כל פעם.

קוד PHP:

 for (int i = 0; i < a.Length; i++)
            {

                randomum = r1.Next(0, l2.Count-1);


                a[i] =l2[randomum];
                l2.RemoveAt(randomum);

            } 


Ramboli

60 שניות על סיבוכיות:

כשרוצים לאמוד זמן ריצה של אלגוריתם משתמשים במושג סיבוכיות. לא מדובר ב"זמן ריצה" שלו כי זה משתנה כמובן ממחשב למחשב, או אפילו באותו מחשב בריצות שונות (כתלות של עומס על המחשב בנקודות זמן מסויימת).

האומדן נעשה כמספר הפעולות שהאלגוריתם מבצע כתלות בגודל הקלט. אני לא אכנס כרגע להגדרות מתמטיות של חסמים עליונים ותחתונים, אבל בדר"כ משתמשים בסימון [tex]\Theta[/tex] שמסמן "חסם הדוק" (גם חסם תחתון וגם חסם עליון).


לדוגמא, כאשר [tex]n[/tex] הוא גודל הקלט:

סריקת מערך, איבר-איבר: [tex]\Theta (n)[/tex]

מיון מערך בעזרת bubble-sort: [tex]\Theta (n^2)[/tex] (בלי להתייחס למקרה הטוב ביותר, בו המערך כבר ממויין, ואז מדובר ב [tex]O(n)[/tex])


בנוגע לשאלה שלך:

בגלל שרשימה מקושרת לא בהכרח יושבת באופן רציף בזיכרון, גם אם אתה יודע את האינדקס שאתה רוצה למחוק, המחשב עדיין צריך לרוץ על כל האיברים בה, מהראשון עד לאינדקס הרצוי, לכן גם מדובר ב- [tex]\Theta (n)[/tex]

Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. -Rick Cook

List ב-C# זה Array List כלומר מימוש של רשימה בעזרת מערך.
זמן גישה לאיבר ב-Array List הוא קבוע. הבעיה היא שכאשר מסירים אותו צריך להעתיק את כל האיברים שאחריו מקום אחד אחורה.

כמו שנאמר, [tex]\Theta(nk)[/tex] אומר שהאלגוריתם רץ בזמן שהינו סדר גודל של [tex]nk[/tex] (את ההגדרות המדויקות אפשר למצוא למשל כאן רק זה עלול לעלות בקצת כאב ראש).
[tex]\log x[/tex] היא פונקציה שעולה לאט מאוד יחסית ל-[tex]x[/tex]. לכן [tex]\Theta(k\cdot \log k)[/tex] ו-[tex]\Theta(n)[/tex] מהווים שיפור משמעותי מהאלגוריתם שהצעת.
לא צריך ידע מיוחד כדי למצוא את האלגוריתמים הנ"ל למעט אולי זה שצריך לדעת את זמן הריצה של מיון מערך.

זהירות - ספויילר!

1. לבחור מס' רנדומלי בין 0 למס' האיברים ברשימה
2. להוסיף את המס' לרשימה חדשה של אינדקסים של איברים שכבר נבחרו, עם ווידוא שהוא לא קיים כבר
3. חוזר על סעיף 1, עד כמות של K פעמים
4. להחזיר את הרשימה החדשה

שני:

זהירות - ספויילר!

1. לבחור מס' רנדומלי בין:
i*N/K
לבין

קוד:

(i+1)*N/K

ולהוסיף לרשימה חדשה של אינדקסים
2. לחזור על סעיף 1 כל עוד i קטן מ- K-1
3. להחזיר את הרשימה של האינדקסים

הרעיון הוא לחלק את N ל-K תחומים, ומכל תחום בוחרים מספר באופן רנדומאלי...

הרנדומליות נפגעת, אז אפשר קצת לשפר אותה בעזרת בחירת הטווח בין המס' הרנדומלי האחרון שנבחר לבין "התחום הבא"...

עריכה:

שלישי:

זהירות - ספויילר!

Init: i=0
1. לבחור מס' רנדומאלי בין i ל-N
2. להחליף את המס' שבאינדקס בסעיף 1 עם המספר במיקום i
3. להגדיל את i ב-1, ולחזור על סעיף 1 עד ש-i=k

את השלישי ממש אהבתי! D=

הפתרון הראשון מצריך ניתוח של בעיה הנקראת בעית איסוף הקופונים. מספר הפעמים שצריך לחזור על סעיף 1 הוא בממוצע [tex]n\cdot\left(\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+\cdots+\frac{1}{n-k+1}\right)[/tex]. זה סדר גודל של [tex]n\cdot\log k[/tex]. צריך להסביר איך אתה בודק אם האיבר נמצא כבר ברשימה כדי לנתח את זמן הריצה.

הפתרון השני, כמו שציינת, אינו מתאים להגדרת הבעיה בה אנחנו מעוניינים בסיכוי שווה לכל בחירה. בכל מקרה, זמן הריצה שלו הינו [tex]\Theta(k)[/tex] (שזה הכי טוב שאפשר לצפות).

הפתרון השלישי זה אחד מהפתרונות שרמזתי אליו. כל הכבוד. הוא לוקח [tex]\Theta(n)[/tex] כי צריך להעתיק את המערך ע"מ לא לשנות אותו. עכשיו כשאני חושב על זה אפשר לשפר אותו ל-[tex]\Theta(k)[/tex], רעיונות?

ציטוט:

במקור נכתב על ידי Idjo הפתרון השלישי זה אחד מהפתרונות שרמזתי אליו. כל הכבוד. הוא לוקח [tex]\Theta(n)[/tex] כי צריך להעתיק את המערך ע"מ לא לשנות אותו. עכשיו כשאני חושב על זה אפשר לשפר אותו ל-[tex]\Theta(k)[/tex], רעיונות?

זהירות - ספויילר!

הפתרון הכי טוב שאני חושב עליו כרגע זה לבצע את הפתרון השלישי שכבר הצעתי, שבסופו פשוט מחזירים את האיברים למקומותיהם המקוריים ושומרים את האינדקסים שלהם ברשימה נוספת.
ואז אין צורך ליצור העתק של הרשימה המקורית.
אני מניח שזה יוצא סיבוכיות של 2K..?

איך אתה מבצע את ההחזרה?
סיבוכיות של 2k ו-k זה אותו הדבר.

כתבתי פסבדו קוד בשביל הדוגמא..:

קוד:

int i=0
int rnd # Holds a random number
int tmp # Helps with the swapping
int K=10
int N=100
int results[K] # The list of unique numbers that we found
int input[N] = {...} # The list with the data

# Pick the unique numbers
while (i < K) { 
  
  rnd = random(i,sizeOf(N))
  
  results[i] = rnd

  tmp = N[rnd]
  N[rnd] = N[i]
  N[i] = tmp
  
  i += 1
}

# Restore the list to it's original order
i = 0
while (i < K) {

  tmp = N[results[i]]
  N[results[i]] = N[i]
  N[i] = tmp
  
  i += 1
}

אני בעצם שומר את המספרים הרנדומליים שקיבלתי ואז יודע איזה איבר מתאים לאיזה מקום..

אבל מה האלגוריתם שאתה חשבת עליו? זה משהו אחר..?

מצוין, אבל צריך לעשות את ההחזרה הפוך כדי שזה יעבוד נכון (וגם התיאור של results שגוי):

קוד:

init randoms of size k
init results of size k

for i = 0 to k-1
  randoms[i] = random number between i and n-1
  switch between A[randoms[i]] and A[i]
  results[i] = A[i]

for i = k-1 down to 0
  switch between A[randoms[i]] and A[i]

return results

זה אכן האלגוריתם עליו חשבתי. לגבי הפתרון השני, אני צריך לחשוב עליו שוב כי פתאום אני לא בטוח שהוא נכון. בכל מקרה, לפתרון הזה יש את הזמן ריצה הכי טוב (מבחינה אסימפטוטית).

זהירות - ספויילר!

האמת שאני לא מבין בשביל מה בכלל צריך ריצות על מערכים.
אפשר לדעתי להגריל k מספרים רנדומליים 1 עד n
ולהעתיק למערך חדש את האינדקסים:
[TEX]i_1[/TEX]
[TEX]i_1+i_2[/TEX]
[TEX]i_1+i_2+i_3[/TEX]
וכן הלאה.. (מודולו n כמובן)

איזה זמן ריצה זה?

תוספים לפורום
קורס לטינית בלעדי לפרש, בפורום שפות ובלשנות.

איך בדיוק אתה מבטיח שלא תהיינה חזרות? מה שהצעת לא שונה מסתם הגרלה של k מספרים בין 1 ל-n.

כן, קלטתי את זה בדיעבד.
אני מאשים את השעה.

תוספים לפורום
קורס לטינית בלעדי לפרש, בפורום שפות ובלשנות.

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

לא הבנתי את השלישי, את סעיף 2

Ramboli

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

קוד:

int i=0
int rnd # Holds a random number
int tmp # Helps with the swapping
int K=10
int N[100] = {...}

while (i < K) { # Part of clause 3
  
  rnd = random(i,sizeOf(N)) # Clause 1
  
  # Starting clause 2
  tmp = N[rnd]
  N[rnd] = N[i]
  N[i] = tmp
  # Ending clause 2
  
  i += 1 # Part of clause 3
}

http://en.wikipedia.org/wiki/Fisher...93Yates_shuffle

תודה לשניכם, אני בנתיים אשאר עם האלגוריתם הזה כי הוא עובד בסדר.

Ramboli

כמו כל הבעיות בעולם דונלד קנות' כתב את הפתרון בספר....

http://en.wikipedia.org/wiki/Fisher...93Yates_shuffle

אני לא רואה בקישור ששניכם הבאתם פתרון יעיל כמו שהוצע כאן לבחירת k איברים מתוך n.
שאלת המשך מעניינת: כמה טוב אפשר להשיג אם אסור לשנות את המערך המקורי אפילו באופן זמני? (יש לי רעיון לזמן של [tex]\Theta(k)[/tex] במקרה הממוצע)

ציטוט:

במקור נכתב על ידי Idjo אני לא רואה בקישור ששניכם הבאתם פתרון יעיל כמו שהוצע כאן לבחירת k איברים מתוך n. שאלת המשך מעניינת: כמה טוב אפשר להשיג אם אסור לשנות את המערך המקורי אפילו באופן זמני? (יש לי רעיון לזמן של [tex]\Theta(k)[/tex] במקרה הממוצע)

אני רואה שם את ההצעה השלישית של dorM:
בוחרים מספר אקראי בין 1 לטווח העליון. בוחרים מספר בין 1 לטווח העליון-1. בוחרים מספר בין 1 לטווח העליון-2. בוחרים מספר בין 1 לטווח העליון-3... ממשיכים כך עד שמסיימים לבחור את k האיברים שרצינו.

בהתחלה המספר הוא האינדקס (כשסופרים מ-1) במערך.

בבחירה השנייה זה האינדקס שממופה למערך כך שאם הוא גדול מ-[TEX]i_1[/TEX] זה האינדקס במערך, ואם הוא גדול או שווה ל-[TEX]i_1[/TEX] אז בוחרים את האלמנט ה-[TEX]i_1+1[/TEX] במערך.

בבחירה השנייה זה האינדקס שממופה למערך כך:

• אם [TEX]i_3<min(i_1,i_2)[/TEX] זה האינדקס במערך.
• אם [TEX]min(i_1,i_2) < i_3 < max(i_1,i_2)[/TEX] אז בוחרים את האלמנט ה-[TEX]i_3+1[/TEX] במערך
• אם [TEX]i_3>max(i_1,i_2)[/TEX] אז בוחרים את האלמנט ה-[TEX]i_3+2[/TEX] במערך.

וכך הלאה. כדי להקל את המיפוי הזה, כל פעם מחליפים בין האלמנט שבחרנו לאלמנט העליון במערך,ועוברים לעבוד בתת-מערך [קצה_תחתון : קצה_עליון-1].

זה בדיוק מה שכתוב בקישור בויקיפדיה.

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

כן צודק, לא משנה. הצעות איך לעשות את זה בלי לגעת במערך?

ציטוט:

במקור נכתב על ידי Idjo כן צודק, לא משנה. הצעות איך לעשות את זה בלי לגעת במערך?

לי זה נשמע סבבה.
מה הסיבוכיות של הוצאת איקס כדורים משק ללא חזרות? או-גדול-של-איקס. ספציפית, זה איקס ממש.
מה הסיבוכיות פה? כנ"ל.

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

לא הבנתי.
הסכמתי איתך שהאלגוריתם שם אכן עושה זאת בזמן הטוב ביותר.
ללא קשר לכך, הצעתי אתגר לתת אלגוריתם יעיל ככל האפשר שעושה זאת כאשר נתון שהמערך המקורי הוא לקריאה בלבד.

ציטוט:

במקור נכתב על ידי Idjo לא הבנתי. הסכמתי איתך שהאלגוריתם שם אכן עושה זאת בזמן הטוב ביותר. ללא קשר לכך, הצעתי אתגר לתת אלגוריתם יעיל ככל האפשר שעושה זאת כאשר נתון שהמערך המקורי הוא לקריאה בלבד.

ערכת את התגובה שלך! (בתוך שתי הדקות)
כשקראתי היה כתוב שם משהו אחר, ולא שמתי לב כשלחצתי על ציטוט שכבר מצוטט הטקסט הערוך.

מה לעשות כשהמערך לקריאה בלבד? צריך לחשוב על זה קצת, אבל בשלוף הייתי אומר לשמור את האינדקסים שאנחנו בוחרים, ולבצע את התהליך שתיארתי בהתחלה, לפני הטריק של ההחלפות, אבל זה יוצא n*k. צריך לחשוב עוד טיפה.

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

חשבתי בהתחלה שאולי קראת את התגובה הקודמת אבל ראיתי שציטטת את התגובה החדשה

אני מציע לך להתעמק באלגורית המקורי, לא של קנות'...
ההארה תבוא משם