Re: Combination of binary variables

Nightfall wrote:

this is my problem: let's take an array of n binary variables. I
need an algorithm to write every possible combination of those
variables.

If, say, n = 3, the algorithm should output:

000
001
010
100
011
110
101
111

I have to implement this algorithm in Mosel language (the
language used in Xpress-Optimizer), but this does't matter:
can you help me with just some "pseudo-code", please?

Here's some real code:

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

/* Public domain, by C.B. Falconer. *//* 2003-Aug-21 */
/* Attribution appreciated. */

/* Things get out of hand when larger than 8 */
#define MAXWORD 12

/* ------------------ */

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd[i];
wd[i] = c;
} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring);
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */

/* ------------------ */

int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];

if (argc < 2) {
fprintf(stderr,
"Usage: jumble <baseword> [lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

min = lgh;
if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;

for (n = lgh, max = 1.0; n > (lgh - min); n--)
max = max * n;

fprintf(stderr, "string=\"%s\", max=%.0f, len=%u\n",
argv[1], max, min);

jumble(argv[1], lgh, 0, min, outstring);
return 0;
} /* main */

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>



--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • [PATCH 1/5] AF_RXRPC: Add blkcipher accessors for using kernel data directly
    ... Also add a CRYPTO_ALG_DMA algorithm capability flag to permit or deny the use ... If kernel data is going to be accessed directly, then CRYPTO_ALG_DMA must, for ... struct scatterlist *dst, struct scatterlist *src, ... unsigned int min_keysize; ...
    (Linux-Kernel)
  • [PATCH 1/5] AF_RXRPC: Add blkcipher accessors for using kernel data directly [try #2]
    ... Also add a CRYPTO_ALG_DMA algorithm capability flag to permit or deny the use ... If kernel data is going to be accessed directly, then CRYPTO_ALG_DMA must, for ... struct scatterlist *dst, struct scatterlist *src, ... unsigned int min_keysize; ...
    (Linux-Kernel)
  • Re: Nested loop with no overlap
    ... > levels nested loops (i.e. one loop inside another one for 5 levels ... > of "for") all the loops are for the same integers range. ... string wd of length lgh into outstring at index ix. ... void jumble(char *wd, unsigned int lgh, ...
    (comp.programming)
  • Re: division problem
    ... unsigned int dividend: ... division instructions to accomplish a larger division, ... then go on to the next digit. ... The classic algorithm assumes that the machine has a division instruction ...
    (comp.lang.c)
  • Re: Combinations in C?
    ... /* Form all n char permutations of the characters in the ... string wd of length lgh into outstring at index ix. ... void jumble(char *wd, unsigned int lgh, ...
    (comp.lang.c)