## 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();
}
}