Это простой способ перетасовать список в AppleScript?

Question

Это простой способ перетасовать список в AppleScript?

Я сделал несколько поисков и нарисовал пробел.

Answer 1

Сокращенный вариант алгоритма Фишера-Yates:

on shuffle(l) 
    set i to count of l 
    repeat while i ≥ 2 
     set j to random number from 1 to i 
     tell l to set {item i, item j} to {item j, item i} 
     set i to i - 1 
    end repeat 
    l 
end shuffle 

set l to {} 
repeat 1000 times 
    set end of l to random number from 1 to 1000 
end repeat 
shuffle(l) 

Есть я * ... * 2 = я! возможные последовательности случайных чисел. Все они соответствуют точно одной перестановке из i! перестановки в списке.

Более быстрая версия, которая использует объект сценария:

on shuffle(input) 
    script s 
     property l : input 
    end script 
    set i to count of l of s 
    repeat while i ≥ 2 
     set j to random number from 1 to i 
     set {item i of l of s, item j of l of s} to {item j of l of s, item i of l of s} 
     set i to i - 1 
    end repeat 
    l of s 
end shuffle 

Сценарии приняли около:

• 0.15 и 0.06 секунды на 1000 элементов
• 12 и 0,5 секунды для 10000 элементов
• 976 секунд и 4 секунды для 100000 элементов

Итак, первый сценарий имел экспоненциальную временную сложность. Сценарии, опубликованные регулусом, были немного медленнее.

Когда я сохранил первый скрипт как scpt и добавил в список 10000 элементов, я столкнулся с limit for the number of items that can be saved in a compiled script.

Answer 2

Я думаю, что я взломал его. Завершена функция для удобства использования.

set myList to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 

set answer to listShuffle(myList) 


on listShuffle(theList) 

set listLength to count of theList 

repeat while listLength > 1 



    set r to random number from 1 to listLength 

    set item1 to item listLength of theList 
    set item2 to item r of theList 

    set item listLength of theList to item2 
    set item r of theList to item1 

    set listLength to listLength - 1 

end repeat 

return theList 

end listShuffle 

Answer 3

Вот альтернатива. Вместо того, чтобы «перетасовка» список, мы просто случайно захватить элементы из списка и вставить их в новый список ...

set myList to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 
set randomizedList to randomizeList(myList) 

on randomizeList(theList) 
    set listCount to count of theList 

    set newList to {} 
    repeat listCount times 
     set subListCount to count of theList 
     set r to random number from 1 to subListCount 
     set end of newList to item r of theList 

     -- remove the random item from theList 
     if subListCount is 1 then 
      exit repeat 
     else if r = 1 then --> first item 
      set theList to items 2 thru end of theList 
     else if r = subListCount then --> last item 
      set theList to items 1 thru -2 of theList 
     else 
      set theList to items 1 thru (r - 1) of theList & items (r + 1) thru -1 of theList 
     end if 
    end repeat 

    return newList 
end randomizeList 

EDIT: если вы хотите, чтобы ускорить действия по большому списку вы можете использовать объект сценария. Вы часто увидите увеличение скорости при большом списке. Таким образом, вы могли бы написать ваш код таким образом, используя объект сценария ...

set myList to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 
set answer to listShuffle(myList) 

on listShuffle(theList) 
    script s 
     property l : missing value 
    end script 
    set s's l to theList 

    set listLength to count of s's l 

    repeat while listLength > 1 
     set r to random number from 1 to listLength 

     set item1 to item listLength of s's l 
     set item2 to item r of s's l 

     set item listLength of s's l to item2 
     set item r of s's l to item1 

     set listLength to listLength - 1 
    end repeat 

    return s's l 
end listShuffle 

Answer 4

Если элементы в вашем новом списке не должны быть уникальными, то вы могли бы использовать очень эффективно

set selectedItemVar to some item of list someItemListVar 

Answer 5

Я просто брошу свое решение. Я лично работаю только с очень короткими списками (около 200 наименований), из которых мне нужно извлечь уникальные случайные подсписки разной длины. Применение этого алгоритма к списку целиком (то есть передача в count of mainList для maxCount) приведет к перетасованной версии исходного списка. Это не построено для скорости, но может быть более доступным для тех, кто не силен в алгоритмах.

on randomizedSublist(mainList, maxCount) 
    set sublist to {} as list 
    repeat with x from 1 to maxCount 
     set oneItem to some item of mainList 
     repeat until sublist does not contain oneItem 
      set oneItem to some item of mainList 
     end repeat 
     set end of sublist to oneItem 
    end repeat 
    return sublist 
end randomizedSublist