2

I will start with an example. Suppose we have an array of size 3 with elements a, b and c like: (where a, b and c are some numerical values)

|1 | 2| 3|
|a | b| c|

(Assume index starts from 1 as shown in the example above)

Now all possible increasing sub-sequence of length 2 are:

12 23 13

so the sum of product of elements at those indexes is required, that is, ab+bc+ac

For length 3 we have only one increasing sub-sequence, that is, 123 so abc should be printed.
For length 4 we have no sequence so 0 is printed and the program terminates.

So output for the given array will be:

ab+bc+ac,abc,0

So for example if the elements a, b and c are 1, 2 and 3 respectively then the output should be 11,6,0

Similarly, for an array of size 4 with elements a,b,c,d the output will be:

ab+ac+ad+bc+bd+cd,abc+abd+acd+bcd,abcd,0

and so on...

Now obviously brute force will be too inefficient for large value of array size. I was wondering if there is an efficient algorithm to compute the output for an array of given size?

Edit 1: I tried finding a pattern. For example for an array of size 4:

The first value we need is :(ab+ac+bc)+d(a+b+c)= ab+ac+ad+bc+bd+cd (Take A=ab+ac+bd) then the second value we need is:(abc) +d(A) = abc+abd+acd+bcd(B=abc) then the third value we need is : (0) +d(B) = abcd(Let's take 0 as C) then the fourth value we need is: +d(C) = 0

But it still requires a lot of computation and I can't figure out an efficient way to implement this.

Edit 2: My question is different then this since:

  1. I don't need all possible permutations. I need all possible increasing sub-sequences from length 2 to n+1.
  2. I also don't need to print all possible such sequences, I just need the value thus obtained (as explained above) and hence I am looking for some maths concept or/and some dynamic programming approach to solve this problem efficiently.
  3. Note I am finding the set of all possible such increasing sub-sequences based on the index value and then computing based on the values at those index position as explained above.
Community
  • 1
  • 1
Karup
  • 2,024
  • 3
  • 22
  • 48
  • Can we assume that the input array will always be sorted ascending order? – Tim Biegeleisen Oct 07 '15 at 06:57
  • @TimBiegeleisen Please check the edit. – Karup Oct 07 '15 at 07:14
  • A sub sequence _is_ a permutation. You are basically doing `r` choose `N`, where `N` is the length of the array. – Tim Biegeleisen Oct 07 '15 at 07:15
  • where `N` varies from 2 to N. So it is `r` choose `2` first, then `r` choose `3` ....till `r` choose `N` and for all of these we need to print the value thus obtained as explain in the question. – Karup Oct 07 '15 at 07:19
  • @TimBiegeleisen Also whether the array is sorted or not doesn't matter since the index will always be sorted. – Karup Oct 07 '15 at 07:20
  • I don't know the solution well, but if I recall the problem correctly, it can be solved using some special matrices and their multiplication. I've googled a little: sorry, can't find neither the problem, nor the solution. – Serge Rogatch Oct 07 '15 at 07:32
  • @SergeRogatch googling "special matrices and their multiplication" didn't lead me anywhere :) It would be really helpful if you could recall a bit more. – Karup Oct 07 '15 at 07:40
  • @fjardon But here author mentions `abc+abd+acd+bcd` and `all possible increasing sub-sequences from length 2 to n+1.` – MBo Oct 07 '15 at 09:46
  • @MBo you're perfectly right – fjardon Oct 07 '15 at 09:48
  • @MBo that's what I was looking for :) – Karup Oct 07 '15 at 13:38

1 Answers1

0

As a post that seems to have disappeared pointed out one way is to get a recurrence relation. Let S(n,k) be the sum over increasing subsequences (of 1..n) of length k of the product of the array elements indexed by the sequence. Such a subsequence either ends in n or not; in the first case it's the concatenation of a subsequence of length k-1 of 1..n-1 and {n}; in the second case it's a subsequence of 1..n-1 of length k. Thus:

S(n,k) = S(n-1,k) + A[n] * S(n-1,k-1)

For this always to make sense we need to add:

S(n,0) = 1
S(n,m) = 0 for m>n
dmuir
  • 4,211
  • 2
  • 14
  • 12