Search Comments and Ratings

go

   
Date File Comment by Comment Rating
10 Mar 2014 Restricted Integer Composition Generates restricted and unrestricted integer compositions Author: Theophanes Raptis iuvaris

Well, it's still my firm view that this algorithm (not the implementation) is awfully slow and no bit more general than other algorithms for restricted integer compositions.

For example, when I set n=16; a=1; b=4; and run

tic; jdoric(n,1,16,a,b); toc

this yields, on my computer, a run time of 21 seconds. Contrarily, when I run

tic; for k=1:16; colex(n,k,a,b); toc

this runs in 2.5 seconds. (Colex is the Vajnovszki/Vernay algorithm that is also available as a matlab implementation).

When I set n=18, run times become 289 seconds and 25.6 seconds, respectively.

So, why on earth would anyone want to use this slow algorithm?

Other issues:
1) The good rating of this algorithm here on mathworks appears to be manipulated.
2) You may wish to google "Corrections" to the Opdyke algorithm "A unified approach ..."

Comment only
13 Jan 2014 Restricted Integer Composition Generates restricted and unrestricted integer compositions Author: Theophanes Raptis iuvaris

Alright, I agree, John D'Errico, that the argumentation should remain factual.

It's just really difficult to argue with Mr. Opdyke because he apparently doesn't understand some basic principles of the things he has published about. Writing problematic papers is one thing, defending errors beyond reason is another. Whatever his contributions in his paper have been, they have neither been the provision of solutions to open problems nor the provision of a general algorithm for solving the restricted integer composition/partition problem. I think that the "success" of his paper is due to self-promotion - and recipients of his work should be made aware of his paper's and algorithm's deficiencies.

In the interest of his readers, I have summarized my points of critique in a pdf file.
http://www.adiuvaris.org/correction.pdf

Comment only
12 Jan 2014 Restricted Integer Composition Generates restricted and unrestricted integer compositions Author: Theophanes Raptis iuvaris

Lastly, JD Opdyke, why do you never mention hirosh tagoya, Mark Headstrom, Nam Quire, Jasper Baxxter?

It's seems your mathwork comments are just as suspicious as your journal publication.

1
10 Jan 2014 Restricted Integer Composition Generates restricted and unrestricted integer compositions Author: Theophanes Raptis iuvaris

Well, it is really extremely simple. The JD Opdyke paper has the following major flaws:

1) The Odyke algorithm takes O(k) time per composition of n with k parts. Thus, the algorithm is inefficient.

2) The counting formulae are copied from previous work and sold as new. It is well-known that the number of compositions of n with k parts, each in a set A, satisfies the recursion:

c_A(n,k) = sum_{a in A} c_A(n-a,k-1)

(see Heubach and Mansour, Compositions of n with parts in a set A, Proof of Theorem 2.1)
Specializing to A={1,...,r} gives the formulas that the JD Opdyke paper derives as "novel".

3) All errors made concerning compositions translate to partitions (which are just ordered compositions)

4) An algorithm that runs in time O(k) per composition needs not solve the restricted integer composition problem in its full generality (arbitrary lower and upper bounds a and b) since the general case can be reduced to a=0.

5) To worsen things for the Opdyke paper, the algorithm solves the problem with upper and lower bounds on the NUMBER OF PARTS in a quite silly way by simply invoking the inefficient Opdyke algorithm for each part.

6) This said, the Vajnovszki algorithm is trivially as general as the Opdyke algorithm is and runs incredibly much faster as k increases since it is not inefficient.

1
06 Dec 2013 Sequence alignment with arbitrary steps Determine the best alignment, with allowed 'steps' <S>, between two sequences Author: iuvaris iuvaris

In the below example, the alignment will be (formatting has been lost below)

x -- y

1 -- 1 3
2 -- 2
2 3 -- 3 2
3 -- 3
2 -- 2
1 -- 1
2 -- 2

Comment only
06 Dec 2013 Sequence alignment with arbitrary steps Determine the best alignment, with allowed 'steps' <S>, between two sequences Author: iuvaris iuvaris

Sample usage would be

x=[1,2,2,3,3,2,1,2];
y=[1,3,2,3,2,3,2,1,2];

steps = [1 1; % substitution/identity
1 2; % expansion
2 1; % squashing
2 2]; % e.g. transposition

[a,v]=seqAlign(x,y,steps,@mysimilarity);
% Output will be in this case
%a =
%
% 1 1 2 1 1 1 1
% 2 1 2 1 1 1 1
%
%v = 18
%
% Return value <a> corresponds to the
% alignment:
%
% 1 2 2 3 3 2 1 2
% 1 3 2 3 2 3 2 1 2
end

function sim=mysimilarity(sub1,sub2);
% just a very silly similarity function
% <sub1> and <sub2> are subsequences

sim=-2;
k1 = length(sub1);
k2 = length(sub2);

if isequal([k1 k2],[1 1])
if sub1==sub2 % 1-1 identity (match)
sim = 3;
end
end

if isequal([k1 k2],[2 2])
if sub1(1)==sub2(2) && sub1(2)==sub2(1) % transposition
sim = 2;
end
end

if isequal([k1 k2],[1 2]) || isequal([k1 k2],[2 1])
sim = sum(sub1==sub2); % in case of squashing or expansion, we let similarity be the number of matches

end

end

Comment only
06 Nov 2013 Restricted Integer Composition Generates restricted and unrestricted integer compositions Author: Theophanes Raptis iuvaris

Again, you may want to look at

http://www.mathworks.com/matlabcentral/fileexchange/44186-restricted-integer-compositions-with-fixed-number-of-parts

for a potentially much faster algorithm based on a different paper.

Comment only
06 Nov 2013 Restricted Integer Composition Generates restricted and unrestricted integer compositions Author: Theophanes Raptis iuvaris

First, thanks to the author for providing this implementation.

However, both the implementation and the algorithm/paper it is based upon are problematic, from my point of view:

(1) Line 41 of the algorithm reads as
if a \le ntmp && ntmp \le b && cell(level+1)

which, if you compare it with the pseudocode in the Opdyke paper, is not correct (it should be cell(level+1)\le b). This is not the only mistake in the implementation.

(2) In the description, it says that the implementation "[...] seems to work pretty fast for integers up to 100". Now, there are \binom{n-1}{k-1} integer compositions of an integer n with k parts and e.g. \binom{100-1}{50-1} is 5.0446e+028. I would be really suprised if this algorithm were "pretty fast" at enumerating all these compositions.

Concerning the Opdyke paper. From my perspective, this paper is highly suspicious and problematic:

(a) The claims concerning the novel formulas that the paper "discovers" are factually wrong. This paper discovers no new formulas. It copies them from the work it cites.
(b) The algorithm presented, to me, is pretty clumsy and it is not clear, to me, what this algorithm is actually doing and whether it is efficient at all (this may be a subjective point of view - I leave it for others to object to this). I think that it might be computing the same things over and over again, which makes it pretty slow, to my opinion. (The paper says that it "almost [never]" does this, but what does this mean?)
(c) To actually test the performance of this algorithm, I implemented the very short and simple algorithm by Vajnovszki, Generating permutations with a given major index, http://arxiv.org/abs/1302.6558, see http://www.mathworks.com/matlabcentral/fileexchange/44186-restricted-integer-compositions-with-fixed-number-of-parts. Both implementations are in matlab, so it is easy to compare. Suppressing the output in both implementations, running times (on an octave platform) for n=20, a=1, b=20, for different values of k (k=mink=maxk in the Opdyke algorithm) are as given below (top is Opdyke, bottom is Vajnovszki). As you can see, except for low k, the Opdyke algorithm is much slower than the Vajnovszki algorithm. E.g., for k=17, running time of the Opdyke algorithm is 22.3 sec vs. 0.079 sec for the Vajnovszki algorithm, whence the Opdyke algorithm is slower by a factor of 282!!

k = 6
Elapsed time is 0.81 seconds.
Elapsed time is 1.3 seconds.
k = 7
Elapsed time is 2.6 seconds.
Elapsed time is 2.8 seconds.
k = 8
Elapsed time is 7.1 seconds.
Elapsed time is 4.9 seconds.
k = 9
Elapsed time is 16 seconds.
Elapsed time is 7.4 seconds.
k = 10
Elapsed time is 27.9 seconds.
Elapsed time is 8.45 seconds.
k = 11
Elapsed time is 41.4 seconds.
Elapsed time is 8.46 seconds.
k = 12
Elapsed time is 52.6 seconds.
Elapsed time is 7.27 seconds.
k = 13
Elapsed time is 57.8 seconds.
Elapsed time is 3.95 seconds.
k = 14
Elapsed time is 55.6 seconds.
Elapsed time is 2.06 seconds.
k = 15
Elapsed time is 46.3 seconds.
Elapsed time is 0.833 seconds.
k = 16
Elapsed time is 33.3 seconds.
Elapsed time is 0.215 seconds.
k = 17
Elapsed time is 22.3 seconds.
Elapsed time is 0.079 seconds.
k = 18
Elapsed time is 13.5 seconds.
Elapsed time is 0.009 seconds.
k = 19
Elapsed time is 7.86 seconds.
Elapsed time is 0.001 seconds.

(d) Finally, it seems that the last couple of comments - those with pretty unusual language and which are so 'euphoric' - are written by the author of the Opdyke paper himself ...

(e) To conclude, I think that this implementation is an accurate copy of the pseudocode presented in the Opdyke paper, with a few mistakes. However, I think that it is highly doubtful whether the Opdyke algorithm is efficient at all. Given the experiments I have outlined, I would judge that the Opdyke algorithm is of no practical value and cannot compete with current state-of-the-art.

2

Contact us