מסיבת ל"ג בעומר עם ילדי הגן של אביב

Some photos from a party with the kindergarden kids of "גן נעים" for ל"ג בעומר

Healy's birth-party

Today we attended Healy's birthday party. She is 2.5 months old.
Here are some shots from the party:

Iterating over permutations of a list

While trying to write down a Perl program that tries to generate XML instances given an XML Schema I stumbled upon the problem of generating instances of xsd:all subtree.

What xsd:all means, basically, is that the listed elements can appear in any order (elements that are listed in an xsd:all can appear 0 or 1 times exactly).

So, in order to do this, the problem reduces to Create an iterator that returns the next permutation of a given list. Why do I want an iterator?

Consider the following implementation:

sub permute {
   my($list)=@_;
   return [[]] unless scalar @$list;
   my @permutations=();
   for(my $i=0; $i<@$list;++$i) {
      my @copy_of_list= @$list;
      my $removed_list_element = splice(@copy_of_list,$i,1);
      push(@permutations, map{[$removed_list_element,@$_]} @{permute(\@copy_of_list)});
   }
   return \@permutations;
}

The permute function receives a reference to a list, say, [ a b c ] and then it returns a list of lists, which is a list of all the permutations of the original list: [ [a b c] [a c b] [b a c] [b c a] [c a b] [c b a] ].

You can see that for a list with N items there are N! permutations.

Note that I'm not discussing lists that contain items that appear more than once. Those actually have less than N! permutations as disarranging places of similar items is meaningless. For example, the permutations of [a b a] are: [ [a b a] [ a a b] [b a a] ] because the remaining 3 permutations are the same.

Notice that the number of permutations grows rapidly as N becomes larger. This makes permute expensive.

We can try to do less calculations in permute by understanding that listing all permutations of two lists of the same length, say N, is actually listing the list of permutations for the list [0 1 2 ... N-1] and then mapping the elements to the proper positions. Combine this with a cache and we get a speedup whenever we want to permute a list of a length that was already computed before. Note also that once you permute a list of length N you also permuted lists of length 1 and of length 2 and so on up until N. So caching also helps when we want to list permutations of smaller lists than computed before.

Let's add a cache to the permute function:

{
   my %cache;
   sub permute {
      my($list)=@_;
      return [[]] unless scalar @$list;
      my $key = join ',',@$list;
      return $cache{$key} if exists $cache{$key};
      my @permutations=();
      for(my $i=0; $i<@$list;++$i) {
         my @copy_of_list= @$list;
         my $removed_list_element = splice(@copy_of_list,$i,1);
         push(@permutations, map{[$removed_list_element,@$_]} @{permute(\@copy_of_list)});
      }
      $cache{$key}=\@permutations;
      return \@permutations;
   }
}    

Our cache is simply a hash. The key to the have is a serialization of the given list elements.

OK, now, but how do we map the elements back onto the list of permutations of indices? Consider the following code:

sub permutmap {
     my($original_list,$indices_lists) = @_;
     my @list_of_lists;
     foreach my $il (@$indices_lists){
             my @l;
             foreach my $i (@$il) {
                     push @l,$original_list->[$i];
             }
             push @list_of_lists,\@l;
     }
     return \@list_of_lists;
}

Which can similarly be implemented without the explicit loops using map:

sub mapermute {
     my($original_list,$indices_lists) = @_;
     return [ map { [map {$original_list->[$_]} @$_] } @$indices_lists ];
}

So all you need now is to feed permute with 1 .. @list and then apply mapermute or permutemap on the result.

Still, I have a problem -- there are too many permutations, listing them is expensive, and not necessarily useful (I might not be able to read them all and use them all). It would be great if I could iterate over the permutations until I have enough, and not generate any permutation beyond the ones that I need. This requires a different approach.

I found a few ones such as:
http://www.perlmonks.org/?node_id=29374
and
http://www.perlmonks.org/?node_id=520116
and also
http://hop.perl.plover.com/announce/07
although the latter hides some of the magic only for subscribers.
You can Google for more results.

Now, let's try and see how to convert my recursion based solution into an iterator.

A colleague at work suggested I take a look at http://en.wikipedia.org/wiki/Permutation#Numbering_permutations
What we can learn from that link is basically:

Numbering permutations

Factoradic numbers can be used to assign unique numbers to permutations, such that given a factoradic of k one can quickly find the corresponding permutation.

Algorithm to generate permutations

For every number k () this following algorithm generates the corresponding permutation of the initial sequence :

 function permutation(k, s) {
    var int factorial:= 1;
    for j = 2  to length(s) {
       factorial := factorial* (j-1);
       swap s[j - ((k / factorial) mod j)] with s[j];
    }
    return s;
}

Notation

• k / j denotes integer division of k by j, i.e. the integral quotient without any remainder, and
• k mod j is the remainder following integer division of k by j.

So, let's see how this translates to Perl:

sub permute {
        my ($k,$s) = @_;
        my @list=@$s;
        my $factorial= 1;
        local $[=1;
        for(my $j=2; $j<=@list;++$j) {
                $factorial*=($j-1);
                my $i=$j-(int($k/$factorial)%$j);
                @list[$i,$j]=@list[$j,$i];
        }
        return @list;
}

Surprisingly, for me, that is, if you iterate over from 1 up to N!-1 rather than up to N! the missing permutation will be the original list itself. I wonder if this is a general property of this formulation/solution and how to prove it.

See:

for (1 .. 6) { # 3! equals 6...
        print permute($_,[qw(a b c)]),"\n";
}

will produce all permutations, while iterating up to 5 will not produce [a b c].

I'm still pondering on what kind of refactoring is required in order to turn my recursive implementation into an iterative one, without using algebric tricks like the above mentioned implementation.

A bug I saw today in the front yard

Here are a few shots of a bug I saw today in the front yard.

Independence Day BBQ

Here are a few pictures from the traditional BBQ party in Independence day. Every year on Independence day we meet at Michal's aunt''s house to celebrate with the family.

Becoming Your Own Boss

I read a nice articles titled "Becoming Your Own Boss" (https://origin.www.spectrum.ieee.org/print/5001 or see: https://origin.www.spectrum.ieee.org/apr07/5001).

I especially liked the advice to start with managing your boss :-)

Birds I saw in the park next door today

Here are a few shots of birds I saw in the park next door today. All of them seems to me as the same bird... :-)

Israel's 59th independence day

Celebrations for Israel's 59th independence day begin this evening.

Today: Israel remembers its fallen fighters

Today is the memorial day for Israel's fallen fighters. In the recent years this memorial day is also dedicated for remembering the many casualties of the terror acts against Israeli citizens.

This evening, the memorial day will end and the celebrations for the 59th year of independence for the State of Israel will begin.

This move from deep sorrow and memorial day ceremonies to the celebrations of the independence day is one of the symbols of this day.

new interview questions

This week's interview questions were prepared for candidates with a background in algorithms in bioinformatics and a few years of C++ experience, with an academic background in statistics. The last two questions in probability are due to Shmuel Fomberg.

.A.

Let S1 and S2 be strings over the same alphabet. The edit distance between S1 and S2 is the smallest number of changes sufficient to transform a substring of S1 into S2, where the changes may be:

1. Substitution --two corresponding characters may differ: KAT -> CAT

2. Insertion -- we may add a character to S1 that is in S2: CT -> CAT

3. Deletion – we may delete from S1 a character that is not in S2: CAAT -> CAT

The cost for every operation is 1, regardless of the operation. Suggest an efficient algorithm for calculating the edit distance between two strings. Suggest a design for an efficient implementation (data structures)

.B.

You have a very large and static text T that you have available a-priory, and a set of strings S that you receive in run-time. Describe a data structure and an algorithm that facilitate efficient multiple queries on the same text. What is the required time complexity for executing a query and getting the result?

.C.

Describe an algorithm for searching the existence of a string S in a text T. Write an implementation in a programming language of your choice. What is the time and space complexity of your solution?

.D.

Describe an algorithm for searching the existence of any string from a set of strings {S1 S2, …, Sn} in a text T What is the time and space complexity of your solution? How will your solution change if you want to know which settings exactly from your set of strings was matched in the text?

.E.

Write an implementation of a function that receives a string containing an arithmetic expression (that has numbers, the +-*/ operators and the parentheses () for precedence ordering) and returns the result of the expression.

.F.

How would you copy a class instance in C++? How would you implement a function that receives the source instance and cloned instance and determines that the two are copies?

.G.

Please suggest an object oriented design for a database layer. So that a developer can write code using an object oriented interface and does not need to know anything about database tables, SQL, etc.

.H.

You have three roads that form a triangle. In every node of the triangle (in every intersection of two roads) there’s one car. At a certain point in time every cars chooses a direction and starts moving. They all start moving at the same time and drive. What’s the probability for a collision? A collision is defined as a meeting where at least one car is headed in one direction and at least one other car is heading in the opposite direction.

.I.

There’s a 95% chance that a car drives by your house within 30 minutes. What is the probability that a car drives by your house within 10 minutes.

Xtech 2007

I'll be attending Xtech 2007 in May. See you there.

Jewish Holocaust Memorial Day

Today is the annual Jewish Holocaust Memorial Day. Here is a good link where you can read all about it: Yad VaShem (יד ושם): http://www.yadvashem.org/

egg shortage

For over a week now there is a shortage of eggs in Kfar Yona. You simply cannot find eggs in the stores.

Yesterday in Petah-Tikva I could not find any eggs other than very expensive ones in מחסני מזון. It looks like the eggs suppliers that normally supply eggs to the stores are not doing do.

I don't have any idea why and I didn't see any information about this in the media.