[Question] From an interview last week

Brussels Sprout

You're given an array of numbers and need to write an algorithm that returns the sum of the numbers for each of the sub-arrays. So for example if you were given the input array {a,b,c}. The output should give:

a+b+c,
a+b,
b+c,
a+c,
a,
b,
c
and finally a blank to represent an empty array.

This problem gave me great difficulty and I took a long time to answer it. At the time I came up with an ugly solution involving a load of nested for loops that wasn't very dynamic and probably wouldn't have worked.

I felt that there was probably a neat recursive solution but I just wasn't seeing it at the time.

What I've since come up with is a solution that copies the array into a series of Lists (C#) and then cycle through these lists removing one element at a time. So using this it is easy to create the arrays {a,b}, {a,c} and {b,c}. The trouble then though is moving to the next stage as using this again results in a lot of repetition of sub-arrays so this doesn't seem like a very efficient solution.

Is there a cleaner solution that someone can spot?

srsly78

http://www.codeproject.com/Articles/37215/Permutations-in-C-Using-Recursion

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

Interesting articles. Was really surprised to find out c++ stl has a built in next_permutation algorithm, but c# doesn't

Aswerty

Spent about 25 minutes on the problem (I love trying out interview questions). The method to approach it I thought up quickly but implementing it with the aid of VS still took just over 20 minutes. This was mainly down to I haven't worked at the bit level recently. Still a bit too long for an interview situation considering it would more than likely be on the white board to boot.

My approach was:

1. To generate the array of numbers.
2. Get the length of the array.
3. Find the number of sub array summations that can be carried out (in this case this is 2^n with n being the number array length).
4. Then I create a for loop that counts in binary up to the 2^n value. A binary value of 110 would equate to (1*4) + (1*6) + (0*7).
5. The inner for loop deals with summing the values together as well as shifting and masking the bits so the appropriate bit is associated with the appropriate number.

Surprisingly this worked on the first run. It should also scale well if the number array is increased or decreased to any reasonable value.

static void Main(string[] args)
{

int[] numberList = { 4, 6, 7};
int listLength = numberList.Length;
int numPerm = (int)Math.Pow(2, listLength);
List<int> sum = new List<int>();

for (byte i = 0x01; i < numPerm; i++)
{
int temp = 0;

for (int j = 0; j < listLength; j++)
{
temp += numberList[j] * ((i >> j) & 0x01);
}

sum.Add(temp);
}

foreach (int integer in sum)
{
Console.WriteLine(integer);
}

Console.Read();

}
}

Brussels Sprout

Thanks for that. That's a very elegant solution.

I'm not too sharp on bitwise operators so I'm going to have to do a bit of research before I fully understand all the code but the logic makes perfect sense to me.

What is the meaning of the term 0x01 though?

Edit: I see now that's the hexadecimal equivalent of 00000001 in binary but could you not just write this as 1?

Aswerty

Yeah there is no problem writing it as 1. What I'm using it for is to mask the other bits such that if I have 110 and I shift left (>>) by 1 to 011 and then apply the mask I get 001 since 011 & 001 = 001. Alternatively 010 & 001 = 000. I use the hex value because I find it a lot more readable than using int values, to be honest I'd of used a binary value if I remembered the syntax because masking is done in a binary context.

http://en.wikipedia.org/wiki/Mask_(computing) is a good article on different types of masking. Also I use shifting (>>) also well described by Wikipedia http://en.wikipedia.org/wiki/Circular_shift. Both fundamental operations at the binary level.

Edit: Actually it appears C# doesn't even have binary literals http://stackoverflow.com/questions/594720/c-sharp-binary-literals

Brussels Sprout

Good stuff. I recall using a mask to generate a version of Conway's Game of Life as a college assignment last year but I'd completely forgotten the operators. I've gone back through my notes and now your code makes perfect sense. Thanks once again!

boblong

Probably not as fast, but a small solution in Haskell:

>> import Data.List

>> (\x -> let l = subsequences x in map (foldl (+) 0) l)[1,2,3]

Brussels Sprout

boblong wrote: »

Probably not as fast, but a small solution in Haskell:

Can you explain what's going on in that code? I'm not familiar with Haskell.

boblong

Brussels Sprout wrote: »

Can you explain what's going on in that code? I'm not familiar with Haskell.

Sure:

\x ->

Is the start of a lambda expression, which long story short takes in something called x.

let l = subsequences x

l is now the sublists of x.

map (foldl (+) 0) l)

The trickiest part to understand - the "(foldl (+) 0)" part is a fold, which lets you apply an operation (in this case plus) across a list and accumulate it onto a starting value. So if you said foldl (+) 0 [1,2,3] you'd get 0+1+2+3 = 6. The map then applies this fold onto each sublist, collecting the results into a new list.

Brussels Sprout

Ah ok, so Haskell has a built in function that returns the sublists of a list. That's pretty handy. I wonder what the guy would have said if I had come up with that as a solution!

Edit: As a programming language, Haskell seems to have a lot in common with Mathematica

Giblet

It can be done in a similar way with F# either, although you would have a bit more to write to get the permutations from an array.