Mathematics and Algorithms
Blog about Mathematics, Functions and Algorithms
- Details
- Written by Super User
- Category: Mathematics and Algorithms
- Hits: 2109
When I first started looking for a fast fourier transformation FFT I was confused, since there are so many different algorithms. Finally I ended up using 2 different algorithms, since one was very powerfull but not so easy to understand, the other was realy easy to understand, but not very efficient.
The first algorithm is called butterfly. This is a very efficient algorithm, and I use them for image processing and transformation of large data signals (TButterflyFFT).
The second I call divide and conquere (TSymetricFFT).
See also the entry: Fast Fourier Transformation in Zeus for C++
- Details
- Written by Super User
- Category: Mathematics and Algorithms
- Hits: 2089
Generating permutations is not very hard and normaly the algorithm are quite simple. But when I looked into traversing permutation using an iterator I had to invent some. Lets look first at the simple case witch just generates all permutations. I finally came up with two possible solutions:
1. traversing the derivation tree
This example looks at a tree. The root node is always empty. The first layer are all nodes containing one unique symbol out of the alphabet. The 2nd layer contains all possible strings containing 2 unique symbols etc.
01 printPerm(slist, tlist)
02 begin
03 if slist.isEmpty then print permutation in tlist
04 else
05 begin
06 for each item in slist do
07 slist':= slist / { item };
08 tlist':= tlist union { item };
09 printPerm(slist', tlist');
10 end
11 end
12 end
As we can see this is not very usefull for iterations.
2. Traversing the tree with iterator
This is algorithm is a little bit more involved. Actually it's a extension to the first one. We simply keep track of each iterator position. Therefore we use for each level of the tree an iterator. Whenever we backtrack we reset the iterator (line 20).
01 perm:= getNextPerm()
02 begin
03 i:= 0;
04 repeat
05 it <- source.iterator[i];
06
07 if it.hasNextUnmarkedItem then
08 begin
09 item <- it.nextUnmarkedItem;
10
11 mark item;
12 perm.push( item );
13 i++;
14 end
15 else
16 begin
17 i--
18 item = perm.pop
19 unmark item
20 it.reset();
21 end
22 until( i = source.length and i >= 0)
23 end
ZeusBase implementation
ZeusBase has been extended with the permutation class TPermutation. The use is quite simple:
01 TPermutation Perm(4); // with 4 elements
02 while(Perm.hasNextPerm())
03 {
04 TIterator<Int> It = Perm.getNextPerm().getIterator();
05 TString strOut;
06 while(It.hasNextItem())
07 {
08 strData += It.getNextItem();
09 }
10 printf("\nPerm: %s", strOut.c_str());
11 }
The TPerumtation class returns each time a list with the indices 1 to 4. These indices might be used as a lookup for other data structures such as string list, arrays etc.