Prev: Generating ordered subsets of fixed size. Was Re: Algorithms?
Next: Fuzzy Search / Input Rules
From: James Dow Allen on 15 Jul 2010 15:28
On Jul 15, 10:41 pm, Frederick Williams
<frederick.willia...(a)tesco.net> wrote:
> I have an array of 48 (ish) positive integers arranged in order of
> increasing magnitude without repetitions.  I wish to create all
> 6-element sub-arrays maintaining the order.

I'll attach a version of the C code I use. It operates only
on the set {0,1,2,3,...,47} so you'll need to set up an array
with the 48 elements you really want and use these as indexes
into that.

The weird-looking algorithm is one in Knuth.

James Dow Allen

#include <stdio.h>

int comb_nxt(int *arr)
{
int j, k, a0, a1;

k = *arr++;
a0 = arr[0];
a1 = arr[1];
if (k & 1) {
if (a0 + 1 < a1) {
arr[0] = a0 + 1;
return 1;
}
j = 1;
} else if (a0 > 0) {
arr[0] = a0 - 1;
return 1;
} else if (a1 + 1 < arr[2]) {
arr[0] = a1;
arr[1] = a1 + 1;
return 1;
} else {
j = 2;
a0 = a1;
a1 = arr[2];
}
while (j < k) {
if (a1 > j) {
arr[j] = a0;
arr[j - 1] = j - 1;
return 1;
}
a0 = a1;
a1 = arr[++j];
if (a1 + 1 < arr[j + 1]) {
arr[j - 1] = a1;
arr[j] = a1 + 1;
return 1;
}
a0 = a1;
a1 = arr[++j];
}
return 0;
}

#define SIZE_UNIV 48
#define SIZE_SSET 6

int combix[SIZE_SSET + 2] = {
SIZE_SSET, 0, 1, 2, 3, 4, 5, SIZE_UNIV,
};

/* gcc -Wall -O -o simpcombo simpcombo.c */
int main(int argc, char *argv[])
{
int i;

do {
for (i = 1; i <= SIZE_SSET; i++)
printf(" %d", combix[i]);
printf("\n");
} while (comb_nxt(combix));
return 0;
}
/* End of sample program */
From: mohangupta13 on 15 Jul 2010 15:32
On Jul 15, 9:03 pm, S Perryman <a...(a)a.net> wrote:
> Frederick Williams wrote:
> > I have an array of 48 (ish) positive integers arranged in order of
> > increasing magnitude without repetitions.  I wish to create all
> > 6-element sub-arrays maintaining the order.  I think there are about 12
> > million of them.
to me it seems about 43^6= abt 6.3 million (correct me if i am
wrong )..


 My plan is to create all 5-element sub-arrays and
> > interpolate all single elements that don't disturb the order.  And to do
> > that by creating all 4-element ..., etc.  So, a recursive solution.

It seems you have to access every such block of 6 numbers . Then what
you say should be good ,but all differences can be made the way you
code that algorithm here.

 My
> > question: is that the best way?  Best probably means fastest.
>
> ARRAY = [ 1 2 3 ]
>
> 1. Form a directed graph D from ARRAY.
>
> 1 ---> 2 ---> 3
> +-------------^
>
> 2. Find all paths in D that are of length L.
> L = 2 gives [1,2] , [1,3] , [2,3] .
>
> Should be plenty of "all paths of length L" graph algorithms out there, for
> your desired prog lang.
>
> Regards,
> Steven Perryman

From: James Dow Allen on 15 Jul 2010 15:37
On Jul 15, 10:41 pm, Frederick Williams
<frederick.willia...(a)tesco.net> wrote:
> I have an array of 48 (ish) positive integers arranged in order of
> increasing magnitude without repetitions.  I wish to create all
> 6-element sub-arrays maintaining the order.

(Sorry if my message is a duplicate.)

I've attached a version of the code I use.
It operates only on {0,1,2,3,4,5,...,47}
so you'll need to use the numbers it gives
you as indexes into an array of the values
you really want.

Algorithm, however weird-looking, is from Knuth's book
(and has a special property!)

James Dow Allen


#include <stdio.h>

int comb_nxt(int *arr)
{
int j, k, a0, a1;

k = *arr++;
a0 = arr[0];
a1 = arr[1];
if (k & 1) {
if (a0 + 1 < a1) {
arr[0] = a0 + 1;
return 1;
}
j = 1;
} else if (a0 > 0) {
arr[0] = a0 - 1;
return 1;
} else if (a1 + 1 < arr[2]) {
arr[0] = a1;
arr[1] = a1 + 1;
return 1;
} else {
j = 2;
a0 = a1;
a1 = arr[2];
}
while (j < k) {
if (a1 > j) {
arr[j] = a0;
arr[j - 1] = j - 1;
return 1;
}
a0 = a1;
a1 = arr[++j];
if (a1 + 1 < arr[j + 1]) {
arr[j - 1] = a1;
arr[j] = a1 + 1;
return 1;
}
a0 = a1;
a1 = arr[++j];
}
return 0;
}

#define SIZE_UNIV 48
#define SIZE_SSET 6

int combix[SIZE_SSET + 2] = {
SIZE_SSET, 0, 1, 2, 3, 4, 5, SIZE_UNIV,
};

/* gcc -Wall -O -o simpcombo simpcombo.c */
int main(int argc, char *argv[])
{
int i;

do {
for (i = 1; i <= SIZE_SSET; i++)
printf(" %d", combix[i]);
printf("\n");
} while (comb_nxt(combix));
return 0;
}
/* End of sample program */
From: Frederick Williams on 15 Jul 2010 15:50
James Dow Allen wrote:
>
> On Jul 15, 10:41 pm, Frederick Williams
> <frederick.willia...(a)tesco.net> wrote:
> > I have an array of 48 (ish) positive integers arranged in order of
> > increasing magnitude without repetitions. I wish to create all
> > 6-element sub-arrays maintaining the order.
>
> (Sorry if my message is a duplicate.)
>
> I've attached a version of the code I use.

Thank you, that's especially helpful since I'm coding in C.

> It operates only on {0,1,2,3,4,5,...,47}
> so you'll need to use the numbers it gives
> you as indexes into an array of the values
> you really want.
>
> Algorithm, however weird-looking, is from Knuth's book
> (and has a special property!)
>
> James Dow Allen
>
> #include <stdio.h>
>
> int comb_nxt(int *arr)
> {
> int j, k, a0, a1;
>
> k = *arr++;
> a0 = arr[0];
> a1 = arr[1];
> if (k & 1) {
> if (a0 + 1 < a1) {
> arr[0] = a0 + 1;
> return 1;
> }
> j = 1;
> } else if (a0 > 0) {
> arr[0] = a0 - 1;
> return 1;
> } else if (a1 + 1 < arr[2]) {
> arr[0] = a1;
> arr[1] = a1 + 1;
> return 1;
> } else {
> j = 2;
> a0 = a1;
> a1 = arr[2];
> }
> while (j < k) {
> if (a1 > j) {
> arr[j] = a0;
> arr[j - 1] = j - 1;
> return 1;
> }
> a0 = a1;
> a1 = arr[++j];
> if (a1 + 1 < arr[j + 1]) {
> arr[j - 1] = a1;
> arr[j] = a1 + 1;
> return 1;
> }
> a0 = a1;
> a1 = arr[++j];
> }
> return 0;
> }
>
> #define SIZE_UNIV 48
> #define SIZE_SSET 6
>
> int combix[SIZE_SSET + 2] = {
> SIZE_SSET, 0, 1, 2, 3, 4, 5, SIZE_UNIV,
> };
>
> /* gcc -Wall -O -o simpcombo simpcombo.c */
> int main(int argc, char *argv[])
> {
> int i;
>
> do {
> for (i = 1; i <= SIZE_SSET; i++)
> printf(" %d", combix[i]);
> printf("\n");
> } while (comb_nxt(combix));
> return 0;
> }
> /* End of sample program */


--
I can't go on, I'll go on.
From: Frederick Williams on 17 Jul 2010 09:27
mohangupta13 wrote:
>
> On Jul 15, 9:03 pm, S Perryman <a...(a)a.net> wrote:
> > Frederick Williams wrote:
> > > I have an array of 48 (ish) positive integers arranged in order of
> > > increasing magnitude without repetitions. I wish to create all
> > > 6-element sub-arrays maintaining the order. I think there are about 12
> > > million of them.
> to me it seems about 43^6= abt 6.3 million (correct me if i am
> wrong )..

I thought it was 48 choose 6 = 12271512.

--
I can't go on, I'll go on.
 |  Next  |  Last
Pages: 1 2
Prev: Generating ordered subsets of fixed size. Was Re: Algorithms?
Next: Fuzzy Search / Input Rules