You are not logged in.
Pages: 1
In this exercise you have the freedom to chose the type of sequence you want to work with (arrays, lists, vectors, ...) according to the language you're using.
Let's define a "nested sequence" as a sequence where each element can be either:
a value.
a nested sequence
The goal of this exercise is to write a function that will take a nested sequence as input and returns the corresponding "flat" list. For instance:
a = (5, (3, 2), ((5, (3, 2), 4), (2, 1)), 2)
f(a) -> (5, 3, 2, 5, 3, 2, 4, 2, 1, 2)
You should be able to deal with deep nestings. Consider that there is no depth limit.
If your language implements this function, clearly don't use it
Bonus points: Don't use a for loop.
In Javascript, return by reference
function flatten(arr,i,newA)
{
if(arr.length==i)
return -1;
if(typeof(arr[i])=="object")
{
if(flatten(arr[i],0,newA)==-1)
return flatten(arr,i+1,newA);
}
else
{
newA.push(arr[i]);
return flatten(arr,i+1,newA);
}
}
t=[1,[1,2],[2,3]];
g=[];
flatten(t,0,g);
Matlab:
PS; Yes, it's easier for me to include this run on Octaviz than to explain my final one-liner. It's a simple manipulation of matrices, namely transpose (the ' symbol), column assorting (the (:) symbols), and horizontal concatenation of arrays (the horzcat function). If the code is still not clear, then I'll go through it more thoroughly.
[Edit] Well the one liner isn't that clear, so the code goes like this:
flat_x=[]; for (i = 1:size(x'(:)',2)) flat_x = horzcat(flat_x,((x'(:))'{i}'(:))'); end
Where x is any cell matrix.
So, if x is given as:
x = {1,[2,4,5];3,[6,13;2,6]}
then the result would be:
flat_x = [1,2,4,5,3,6,13,2,6]
Note 1: Flattening nested sequences is an inherent property of Matlab, and that's why I decided to step it up and flatten nested matrices instead.
Note 2: This Matlab one-liner code has a very nice real-life application if you think of it. Consider an RGB image; when imported into Matlab/Octaviz, the image is saved as a cell matrix of the binary matrices R, G, and B which compose the image (think of the RGB image as a 3D matrix where R is 1D, G is another 1D, and B is the final 1D). If the binary entries on these matrices were to be transmitted via a channel (let's say emulated in Simulink), then the entries on the matrices would have to be flattened before transmission. I like this exercise :)
[/Edit]
Last edited by mesa177 (October 2 2012)
Working on Python tuples (it can be very easily adapted to other types of sequences), this code takes advantage of the newly introduced yield from syntax.
def flatten_gen(s):
if len(s) > 0:
elt=s[0]
if isinstance(elt, tuple):
yield from flatten_gen(elt)
else:
yield elt
yield from flatten_gen(s[1:])
def flatten(s):
return tuple(flatten_gen(s))
>>> a = (5, (1, 2, (2, 3), (( 5, 4), 3)), (2, 3), (1, (), (2, 5)))
>>> print(flatten(a))
(5, 1, 2, 2, 3, 5, 4, 3, 2, 3, 1, 2, 5)
In PHP; Nothing fancy, just a recursive function with a foreach loop.
I like how readable the code is :)
<?php
$flat_list = $tree = array();
$tree = array(
"one",
array(
"two",
"three",
array(
"four"
),
"five"
),
"six",
"seven",
array(
"eight"
)
);
function descend($into) {
global $flat_list;
if (is_array($into)) {
foreach($into as $item) {
descend($item);
}
} else {
$flat_list[] = $into;
}
}
descend($tree);
print_r($tree);
echo "\r\n";
print_r($flat_list);
?>
See it in action:
http://codepad.org/awXfJqCl
Edit: I had to replace all tabs with spaces in the code for it to display properly. Something is very wrong with the code box.
Last edited by rolf (October 3 2012)
Haskell's equivalent (to a certain extent) to Python's yield from is called concatMap.
data NestedList a =
Elem a | List [NestedList a]
flatten :: NestedList Int -> [Int]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x
Pages: 1