Algorithm to find no. of subsets of size n where each element is smaller than its predecessor with index of 1st element being the least

Question

I have an Array, lets say {7,6,4,2}.

I need an efficient algorithm to find number of times n smaller numbers occur after a given element, where each element is smaller than the preceding one.

For example: for n=3, a[i]>a[j]>a[k] and i < j < k. Here the output should be {7,6,4},{7,6,2} and {6,4,2}.

I have a simple algorithm with 3 for loops but obviously a solution with O(n^3) complexity is not feasible.

Here is the sample code I created for n=3.

// Array is initialized and given values. Size of Array is n1
for(int i=0;i<n1-2;i++)
{
    for(int j=i+1;j<n1-1;j++)
    {
        if(a[j]<a[i])
        {
            for(int k=j+1;k<n1;k++)
            {
                if(a[k]<a[j])
                {
                    cnt++;
                }
            }
        }
    }
}

Could you please link me to an algorithm I could use or provide me with algorithm below. JAVA preferred.

In your code, I don't understand why are you testing the values? Isn't your array sorted? Can you have identical values? — Maxime Chéramy, Feb 05 '15 at 17:07
Array is NOT sorted. You have to find it in the same order. YES there are repeated elements and the counter treats every repetition also as unique — gabbar0x, Feb 05 '15 at 17:09
Just to clarify, the `n` used in your code is the size of the array a, not the `n` used in the problem statement. — Maxime Chéramy, Feb 05 '15 at 17:17
Yeah. It will work regardless of the array being sorted or not. Basically my complexity increases in powers of n. I need an efficient solution. Even if its possible only to make it for a particular n — gabbar0x, Feb 05 '15 at 17:18
Have you considered building a graph and then do a DFS with a limit of n? — Maxime Chéramy, Feb 05 '15 at 17:23
I can suffice with an efficient solution for n=3. But i thought there existed a generalized method for every n. So i included that in the question as well — gabbar0x, Feb 05 '15 at 17:25
I can think of a O(m*n) DP algorithm where m is the value of the maximum value in the array. Theoretically worse, but useful in some contest questions. — Juan Lopes, Feb 05 '15 at 18:06

Maxime Chéramy · Answer 1 · 2015-02-05T17:55:59.060

If you take {7,6,11,2}, you can build a graph where the nodes are 7, 6, 11 and 2 and with an directed edge only if the other node index is greater and it's value lesser. Building such a graph should be O(len(a)^2).

Once the graph is build, you can write a recursive function that count the number of times it can reach 3 successive nodes. Complexity is O(n * len(a)).

My solution (consider only from the first element but it's trivial to adapt):

#include <stdio.h>
#include <stdlib.h>

struct succ {
    struct node* node;
    struct succ* next;
};

struct node {
    struct succ* successors;
    int value;
    int index;
};

struct node* build_graph(int a[], int n1) {
    struct node* graph = malloc(n1 * sizeof(struct node));
    int i, j;
    for (i = 0; i < n1; i++) {
        graph[i].value = a[i];
        graph[i].index = i;
    }

    for (i = 0; i < n1; i++) {
        for (j = i; j < n1; j++) {
            if (a[i] > a[j]) {
                struct succ *el = malloc(sizeof(struct succ));
                el->node = &graph[j];
                el->next = graph[i].successors;
                graph[i].successors = el;
            }
        }
    }

    return graph;
}

int browse(struct node* graph, int i, int n) {
    if (n == 0) return 1;

    struct succ *aux = graph[i].successors;
    int cnt = 0;
    while (aux) {
        cnt += browse(graph, aux->node->index, n - 1);
        aux = aux->next;
    }

    return cnt;
}

int main() {
    //int a[] = {7, 6, 11, 2};
    int a[] = {7, 6, 4, 2};

    struct node* graph = build_graph(a, 4);

    printf("%d\n", browse(graph, 0, 2));

    return 0;
}

I guess it should work but i still have to complete my course on graph theory so yeah :P — gabbar0x, Feb 06 '15 at 07:04

gabbar0x · Answer 2 · 2015-02-06T10:29:55.990

 import java.util.*;
 import java.io.*;    

 class CDVA1510
 {
public static void main(String[] args) throws Exception
 {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in))
    int n=Integer.parseInt(br.readLine());
    String[]a1=br.readLine().split(" ");
    long[] a=new long[a1.length()];
    for(int j=0;j<a.length();j++)
    {
    a[j]=Integer.parseInt(a1[j]); //Storing the values
    }
    ArrayList<Long>al=new ArrayList<Long>();//Sorted List for storing the values
    ArrayList<Integer>nos=new ArrayList<Integer>();//List for adding number of numbers before the given number with which combinations are possible
    int []no=new int[n];
    for(int j=n-1;j>=0;j--)
    {
        al.add(a[j]);
        Collections.sort(al);
        if(al.indexOf(a[j])>=2)//Getting postion of element and since implementation is specific, checking if it it greater than or equal to 2 so that x(this number) choose 2 is possible 
        {
            nos.add(al.indexOf(a[j]));
            //System.out.println(a[j]);
        }
    }
    int cnt=0;
    for(int j=0;j<nos.size();j++)
    {
        cnt += COM(nos.get(j));
    }
    System.out.println(cnt);
}
private static long COM(long a)//Method for getting the combinations. Again specific for n=3
{
    int x=1,y=1;
    for(int i=1;i<=a;i++)
    {
        if(i<=a-2)
        {
            x = x * i;
            y = y * i;
        }
        else
        {
            x=x*i;
        }
    }
    return((x)/(y*2));
}    
}

Algorithm to find no. of subsets of size n where each element is smaller than its predecessor with index of 1st element being the least

2 Answers2