Home > Community > Blogs > Custom IC Design > skill for the skilled using random numbers
 
Login with a Cadence account.
Not a member yet?
Create a permanent login account to make interactions with Cadence more conveniennt.

Register | Membership benefits
Get email delivery of the Custom IC Design blog (individual posts).
 

Email

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

SKILL for the Skilled: How to Shuffle a List

Comments(7)Filed under: SKILL, Team SKILL, programming, LISP, SKILL++, random, IC615, Jim Newton, SKILL for the Skilled, permutations, shuffleThe previous post of SKILL for the Skilled presented some ways to systematically visit all permutations of a list. As noted, the time to iterate through all permutations of a large list is prohibitive. If the goal is to find a permutation that meets some criteria then it may work perfectly well to simply test the criteria on randomly chosen permutations of the list and continue doing so until some time-out is reached. Choosing a permutation at random is also called shuffling.

In this article, I want to look at some ways to shuffle a list. In doing so, we'll also see how random numbers work in SKILL and a few examples of how to use them.

Very easy but not very random

An advantage of the implementation of shuffle_a below is that it very easy to remember and easy to implement. An important disadvantage is that it does a poor job of shuffling the given list. It basically asks the SKILL built-in sort to do the work and provides a compare function for sort to use, which provides some randomness. The SKILL expression (random 2) returns either 0 or 1 selected at random. Consequently the expression (onep (random 2)) returns either t or nil chosen at random.
(defun shuffle_a (data)
  (sort (copy data)
        (lambda (_a _b)
          (onep (random 2)))))
For example, (shuffle_a '(1 2)) returns either (1 2) or (2 1), each with 50% likelihood. However (shuffle_a '(1 2 3)) returns one of the following two permutations half of the time (3 1 2), (3 2 1), and one of the other four permutations the other half of the time. Thus, not all permutations are equally likely.

Similarly, there are 24 permutations of (1 2 3 4), but (shuffle_a '(1 2 3 4)) returns one of the following eight permutations half of the time: (1 2 3 4), (1 2 4 3), (2 1 3 4), (2 1 4 3), (3 4 1 2), (3 4 2 1), (4 3 1 2), or (4 3 2 1). And it returns one of the other 16 permutations the other half of the time.

If you need a quick and dirty shuffle algorithm, shuffle_a is decent and easy to remember. But if you need a good shuffle algorithm, use a different one.

Shuffle by partitioning

The following recursive algorithm can be used to shuffle a list of elements. It works similar to a quick sort, but rather than collecting the large and small elements into two respective lists recursively, it randomly partitions some elements into one sub-list and others into another sub-list, then proceeds to apply the same algorithm recursively onto those two sub-lists.
(defun shuffle_b (data)
  (cond
    ((cddr data) ; more than 2 elements?
     (let (left right)
       (foreach item data
         (if (zerop (random 2))
             (push item left)
             (push item right)))
       (nconc (shuffle_b left)
              (shuffle_b right))))
    ((zerop (random 2))
     (reverse data))
    (t
     (copy data))))

Shuffle by random selection

The following algorithm shuffle_c, works by continuing to randomly choose element at random from the list, push that element onto a new list, and remove it from the old list, continuing until a single element remains, then finally pushing it onto the list.

The expression r = (random n) returns a number 0 <= r < n

(defun shuffle_c (data)
  (let ((n (length data))
        r
        p
        shuffled)
    (while (cdr data)
      ;; choose a random element: data[r]
      r = (random n) ; randomly choose 0 <= r < n
      p = (nthcdr r data)
      
      ;; add data[r] to shuffled
      (push (car p)
            shuffled)
      
      ;; remove data[r] from data
      data = (nconc (ldiff data p)
                    (cdr p))
      
      ;; decrement n
      n--)
    (when data
      (push (car data) shuffled))
    shuffled))

How do you remove an element from a list?

There is a subtle trick in the code for shuffle_c: how to remove an element from a list. The built-in SKILL function remove won't exactly do the trick. Actually, remove works fine if the elements of the list are unique, but not if the list has duplicate elements. The SKILL remove function actually removes all elements from the given list which are equal to the given element. For example (remove 42 '(0 42 1 42 2 42 3)) will return (1 2 3), whereas we want a function, remove_once which works as: (remove_once 42 '(0 42 1 42 2 42 3)) ==> (0 1 42 2 42 3).

You might implement remove_once as follows:

(defun remove_once (data item)
  (let ((p (member item data)))
    (nconc (ldiff data p)
           (cdr p))))
What the shuffle_c function does is chooses an element of the list by position, and then removes the element in that position. For example, given the list mylist=(42 1 42 2 42 3), if we choose the element in position 2 (0-based index), which is the second 42 in the list, we can divide the list in two halves, right and left. The right portion is obtained by calling (nthcdr 2 mylist) ==> (42 2 42 3). The left portion is obtained by left=(ldiff mylist right) ==>(42 1). Given right and left, we can produce a new list equal to the original list but with the element at position 2 removed by appending the two lists left and (cdr right).

How do you select an element at random?

Given a list of elements, the following function will select an element at random from it.
(defun random_element (data)
  (when data
    (nth (random (length data)) data)))
Be careful with this function: if given an empty list, (random 0) triggers an error.

Shorter version of shuffle

The following implementation of shuffle_d is more or less the same algorithm as shuffle_c but uses the helper functions random_element and remove_once.
(defun shuffle_d (data)
  (let (shuffled
        e)
    (while data
      e = (random_element data)
      (push e shuffled)
      data = (remove_once data e))
    shuffled))

Challenge to the reader

If you know another clever way to shuffle a list, please post the code to the comment section of this article below.

Summary

In this article four versions of the shuffle function were presented.
  • shuffle_a: a very short implementation of an inferior sorting algorithm
  • shuffle_b: a recursive divide and conquer shuffle algorithm
  • shuffle_c: an imperative, iterative algorithm for shuffling
  • shuffle_d: similar to shuffle_c but easier because it makes use of helper functions

In addition we looked at two other functions:

  • remove_once: an efficient algorithm for removing a maximum of one element from a list
  • random_element: return a randomly selected element from a list

Comments(7)

By Andrew Beckett on October 9, 2013
Jim,

My gut feeling impression from looking at the implementations was that shuffle_c would suffer badly from performance compared with shuffle_b with large lists. So I did some profiling.

shuffle_b was able to shuffle a million entry list in about 17 seconds; shuffle_c I gave up after about 3 hours. From the profiling so far, it had spent over an hour of that time in gc. So I tried with a list of 10000 entries (2.4 secs), 100000 entries (221 seconds). So my wild guess is that it is of the order of N^2 - and so I might expect a million entries to take roughly 7 hours. shuffle_b was however 0.3 seconds for 10000, and 1.44s for 100000 (and 17 seconds for a million entries).

This doesn't really surprise me because doing those repeated nthcdr can't be very efficient.

I did wonder whether it could be made more efficient by using an array to store the data in the meantime - but the problem then is that you can't really remove entries from an array (such that the indices close up).

Kind Regards,

Andrew.


By Team SKILL on October 9, 2013
Hi Andrew, thanks for the information about the profiling.  I suspected the recursive algorithm might be a little faster.  The results are indeed surprising.

You might be pretty successful by using an array and swapping each element with a randomly chosen element.  I'd want to check the randomness of the resulting list to make sure.  An algorithm such as the following would be where I'd start.

(defun shuffle_array (arr)

 (let ((N (length arr)))

   (for i 0 (sub1 N)

     ;; need to write this function: swap_elements

     (swap_elements arr i (random N)))))

Kind Regards,

Jim


By Andrew Beckett on October 9, 2013
Jim,

Here's an implementation that runs in 5 seconds on a million items, and works by converting to a vector and then back to a list again at the end. I borrowed the algorithm from an implementation I found elsewhere...

(defun shuffle_e (data)

 (letseq (j iinv (vec (listToVector data)) (len (length vec)))

 (for i 1 len

      (setq iinv (difference len i))

      (setq j (random (add1 iinv)))

      (setarray vec iinv (prog1 (arrayref vec j) (setarray vec j (arrayref vec iinv))))

      )

 (vectorToList vec)

 )

 )

Regards,

Andrew.


By Lakshmi Prashanth on April 10, 2014
How to sort this? required help
gc = geGetSelectedSet( )
(db:0x14c97a79 db:0x14c97aca db:0x14c97ad4 db:0x14c97ad1 db:0x14c97ace
   db:0x14c97ab2 db:0x14c97acb db:0x14c97ac8 db:0x14c97ac5 db:0x14c97ac2
   db:0x14c97abe db:0x14c97abf db:0x14c97ab4 db:0x14c97ab7 db:0x14c97ab8
   db:0x14c979a4
)
sort gc
*Error* sort: too few arguments (2 expected, 1 given) - ((db:0x1cdde44d db:0x1cdde44e db:0x1cdde449 db:0x1cdde446 db:0x1cdde445 ... ))
sort (gc nil)
*Error* gc: argument #1 should be a string (type template = "t") - nil
sort (gc 'lessp)
*Error* gc: argument #1 should be a string (type template = "t") - lessp
sort (gc 'alphalessp)
*Error* gc: argument #1 should be a string (type template = "t") - alphalessp

By Team SKILL on April 10, 2014
Hi  Lakshmi,

Thanks for your question.  I think you have space between "sort" and the opening paren.

Remember that in SKILL you are allowed to put the parenthesis either before or after the function name to denote a function call.  Thus (B C) and B(C) are equivalent to each other.  Furthermore (A B C) and A(B C) are equivalent to each other.  Some people refer to these as LISP syntax vs C syntax.

The problem comes when you accidentally try to mix the two.  SKILL does not get confused, but often the human being does.

CIW> (A B (C D))

CIW> (A B(C D))

The first is a call to A with 2 arguments, the second of which is a call to C.

The second is a call to A with 1 argument, namely a call to B.

In summary, if you want to call a function with some arguments, and you want to use C-syntax, don't put a space between the function name and the opening parenthesis.  If you want SKILL to not care where you put spaces, use LISP-syntax.

NOW, back to your example.

CIW> sort (gc nil)

This tries to call sort with the return value of calling gc with nil as its argument.

But if you pass an argument to the gc function (the API for the SKILL garbage collector) that argument must be a string.  This is what the messages mean.

*Error* gc: argument #1 should be a string (type template = "t") - nil

*Error* gc: argument #1 should be a string (type template = "t") - lessp

*Error* gc: argument #1 should be a string (type template = "t") - alphalessp

This explains what your error messages mean, but it does not yet answer your original question.  I'll answer that in the next post.

To be continued.

Jim.


By Team SKILL on April 10, 2014
Hi  Lakshmi,

If you want to sort a list of dbobjects as in your question, which criteria do you want to use to decide how to order them?  Do you want to sort them alphabetically according the the printed representation of their hex addresses. "db:0x14c97a79" < "db:0x14c97b79" ?

Or do you want to sort them by x coordinate of their origin?  Or if it is a list of instances, do you want to sort them alphabetically by cellName?

First you have to decide on the comparison criteria.

If you really want to sort them alphabetically by printed representation, you can try something like the following.

(sort gc (lambda (dbid1 dbid2)
(alphalessp (sprintf nil "%L" dbid1)
(sprintf nil "%L" dbid2))))



Or if you prefer C-syntax, the following is equivalent.

sort( gc lambda( (dbid1 dbid2)
alphalessp( sprintf( nil "%L" dbid1)
sprintf( nil "%L" dbid2))))




By Team SKILL on April 10, 2014
Hi again  Lakshmi,

supposing you want to sort the object according to the x-coordinate of their bounding-boxes.  Here is how you might try it.

(sort gc (lambda (dbid1 dbid2)
(lessp (leftEdge dbid1~>bBox)
(leftEdge dbid2~>bBox))))



You might also take a look at another blog article which actually addresses this question with even more examples.

www.cadence.com/.../skill-for-the-skilled-sorting-with-skill.aspx

Kind regards

Jim


Leave a Comment


Name
E-mail (will not be published)
Comment
 I have read and agree to the Terms of use and Community Guidelines.
Community Guidelines
The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.