Clustered k-Subsets

July 11, 2010 at 04:39 (algorithm, java, math.CO)

This post is mostly copied and pasted from my posts in this thread on MHF.

Problem statement: Let \displaystyle S_n = \{1,\ \dots\ ,n\} and let \displaystyle f(n,k,x) be the number of k-subsets of \displaystyle S_n such that when the elements are ordered from least to greatest, the absolute difference of any two adjacent elements is less than \displaystyle x. Find a formula or algorithm to determine \displaystyle f(n,k,x) for arbitrary \displaystyle n,k,x \in \mathbb{Z}, n\ge 0.

Examples:

\displaystyle f(10,4,2) = 7

\displaystyle x>n-k+1 \implies f(n,k,x)=\binom{n}{k}

My solution is recursive.

First some special cases. We know \displaystyle \forall x<2:f(n,k,x)=0, so assume \displaystyle x\ge2. Also, \displaystyle f(n,0,x)=1.

Let \displaystyle g(n,k,x) be the number of k-subsets of \displaystyle S_n with the same constraint as \displaystyle f(n,k,x) and the additional constraint that each k-subset must contain \displaystyle \{1\}.

Then

\displaystyle f(n,k,x) = \begin{cases}1&,\ k=0 \\ \displaystyle \sum_{i=k}^n g(i,k,x)&,\ 0 < k \le n \\ 0&,\ k<0\ \lor\ k>n\end{cases}

\displaystyle g(n,k,x) = \begin{cases} 1&,\ k=1 \\ \displaystyle \sum_{i=\max(1,n+1-x)}^{n-1} g(i,k-1,x)&,\ 1 < k \le n \\ 0&,\ k<1\ \lor\ k>n\end{cases}

I would be interested in a closed-form expression involving clever combinatorics.

Java code:

public class CombsMaxDiffConsec {
    static int u=100,v=100,w=100;
    static long c,memoG[][][]=new long[u][v][w];
    
    public static void main(String[] args) {
        int i,j,k;
        long t=time();
        System.out.println("Initialising.");
        for(i=0;i<u;i++)
        for(j=0;j<v;j++)
        for(k=0;k<w;k++)
            memoG[i][j][k]=-1;
        System.out.println("Time: "+(time()-t)/1000.0+" seconds");
        t=time();
        System.out.println("\nDoing test cases.");
        // begin test cases
        a(naive(10,4,2)==7);
        a(naive(5,2,3)==7);
        a(naive(5,3,3)==8);
        a(naive(16,4,100)==1820);
        for(i=0;i<10;i++)
        for(j=0;j<=i;j++)
        for(k=2;k<=i-j+2;k++)
            if(k!=6) a(f(i,j,k)==naive(i,j,k));
        // end test cases
        System.out.println("Time: "+(time()-t)/1000.0+" seconds");
        t=time();
        System.out.println("\nUsing fast algorithm:");
        System.out.println("f(80,13,6) = "+f(80,13,6));
        System.out.println("Time: "+(time()-t)/1000.0+" seconds");
        t=time();
        System.out.println("\nUsing naive algorithm:");
        System.out.println("f(80,13,6) = "+naive(80,13,6));
        System.out.println("Time: "+(time()-t)/1000.0+" seconds");
    }
    
    static long f(int n,int k,int x) {
        if(k<0||k>n||x<2) return 0;
        if(k<1||k==n) return 1;
        if(k==1) return n;
        int i;
        long r=0;
        for(i=k;i<=n;i++)
            r+=g(i,k,x);
        return r;
    }
    
    static long g(int n,int k,int x) {
        if(k<1||k>n) return 0;
        if(k<2) return 1;
        if(n<u&&k<v&&x<w&&memoG[n][k][x]!=-1) return memoG[n][k][x];
        int i;
        long r=0;
        for(i=Math.max(1,n+1-x);i<=n-1;i++)
            r+=g(i,k-1,x);
        if(n<u&&k<v&&x<w) memoG[n][k][x]=r;
        return r;
    }
    
    static long naive(int n,int k,int x) {
        if(k<0||k>n||x<2) return 0;
        if(k<1||k==n) return 1;
        if(k==1) return n;
        c=0;
        naive2(k,0,n,x);
        return c;
    }
    
    static void naive2(int r,int j,int n,int x) {
        if(r==0) {
            c++;
            return;
        }
        int i,m=n-r+1;
        if(j>0) m=Math.min(m,j+x-1);
        for(i=j;i<m;i++)
            naive2(r-1,i+1,n,x);
    }
    
    static void a(boolean b) {
        if(!b) throw new AssertionError();
    }
    
    static long time() {
        return System.currentTimeMillis();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: