Data Structures | Files | Defines | Typedefs | Functions

All Permutations Iterator

Data Structures

struct  EGpermIt_t
 Structure to store the information relevant to the permutation iterator. More...

Files

file  eg_perm_it.c
file  eg_perm_it.ex.c
file  eg_perm_it.h

Defines

#define __PERM_IT_NO_INLINE__   0
 choose a macro or function definition of EGpermItNext
#define EG_PERMIT_DBG   0
 Debug level for the heap.
#define EGpermItClear(__gc)
 free all internally allocated memory for the given EGpermIt_t structure.
#define EGpermItGetChange(__gc)   ((const int)((__gc)->changed_pos))
 return which position in the permutation changed in the last iteration.
#define EGpermItGetSize(__gc)   ((const int)((__gc)->sz))
 Return the number of bits for the given permutation iterator.
#define EGpermItGetTuple(__gc)   ((const int*const)((__gc)->tuple))
 Return a constant pointer to the current tuple.
#define EGpermItInit(__gc, __sz)
 Initialize a binary permutation iterator, and set the iterator to the zero position.
#define EGpermItNext(__prit)
 move to the next permutation, if no next string exists (i.e. we finish the loop), return 0, otherwise return 1.
#define EGpermItReset(__gc)
 Reset an initialized permutation iterator to the zero position.

Typedefs

typedef struct EGpermIt_t EGpermIt_t
 Structure to store the information relevant to the permutation iterator.

Functions

int main (int argc, char **argv)
 main function
void prit_usage (char *program)
 given a number, print to standard output a gray code on n bits.

Detailed Description

Here we define an implementation of knuth'__EGs plain changes iterator for permutations of $n$ different elements as defined in ``The Art of Computer Programming, Chapter 7.2.1.2''. We use an algorithms that perform single swaps in each step, the last position of the swap is stored.


Define Documentation

#define __PERM_IT_NO_INLINE__   0

choose a macro or function definition of EGpermItNext

Definition at line 119 of file eg_perm_it.h.

#define EG_PERMIT_DBG   0

Debug level for the heap.

Definition at line 44 of file eg_perm_it.h.

#define EGpermItClear (   __gc  ) 
Value:
do{\
  EGpermIt_t*const __EGgcit = (__gc);\
  EGfree(__EGgcit->tuple);\
  EGfree(__EGgcit->o_focus);\
  EGfree(__EGgcit->c_focus);\
  memset(__EGgcit,0,sizeof(EGpermIt_t));}while(0)

free all internally allocated memory for the given EGpermIt_t structure.

Parameters:
__gc pointer to a permutation iterator structure (EGpermIt_t)
Examples:
eg_perm_it.ex.c.

Definition at line 90 of file eg_perm_it.h.

Referenced by main().

#define EGpermItGetChange (   __gc  )     ((const int)((__gc)->changed_pos))

return which position in the permutation changed in the last iteration.

Parameters:
__gc pointer to a permutation iterator structure (EGpermIt_t)
Examples:
eg_perm_it.ex.c.

Definition at line 115 of file eg_perm_it.h.

Referenced by main().

#define EGpermItGetSize (   __gc  )     ((const int)((__gc)->sz))

Return the number of bits for the given permutation iterator.

Parameters:
__gc pointer to a permutation iterator structure (EGpermIt_t)
Returns:
number of bits for the iterator

Definition at line 102 of file eg_perm_it.h.

#define EGpermItGetTuple (   __gc  )     ((const int*const)((__gc)->tuple))

Return a constant pointer to the current tuple.

Parameters:
__gc pointer to a permutation iterator structure (EGpermIt_t)
Returns:
pointer to an array containing the current tuple
Examples:
eg_perm_it.ex.c.

Definition at line 108 of file eg_perm_it.h.

Referenced by main().

#define EGpermItInit (   __gc,
  __sz 
)
Value:
do{\
  EGpermIt_t*const __EGgcit = (__gc);\
  const int __EGgcsz = __EGgcit->sz = ((int)(__sz));\
  __EGgcit->tuple = EGsMalloc(int,__EGgcsz);\
  __EGgcit->o_focus = EGsMalloc(int,__EGgcsz);\
  __EGgcit->c_focus = EGsMalloc(int,__EGgcsz);\
  EGpermItReset(__EGgcit);}while(0)

Initialize a binary permutation iterator, and set the iterator to the zero position.

Parameters:
__gc pointer to a permutation iterator structure (EGpermIt_t)
__sz number of bits to be used in the iterator.
Examples:
eg_perm_it.ex.c.

Definition at line 77 of file eg_perm_it.h.

Referenced by main().

#define EGpermItNext (   __prit  ) 

move to the next permutation, if no next string exists (i.e. we finish the loop), return 0, otherwise return 1.

Parameters:
__EGprit pointer to a permutation iterator structure (EGpermIt_t)
Returns:
zero if no next string exists, otherwise 1.
Examples:
eg_perm_it.ex.c.

Definition at line 129 of file eg_perm_it.h.

Referenced by main().

#define EGpermItReset (   __gc  ) 
Value:
do{\
  EGpermIt_t*const __EGgcit2 = (__gc);\
  register int __EGgci = __EGgcit2->sz;\
  while(__EGgci--){__EGgcit2->tuple[__EGgci] = __EGgci;\
  __EGgcit2->o_focus[__EGgci]=1;\
  __EGgcit2->c_focus[__EGgci]=0;}\
  __EGgcit2->changed_pos=0;}while(0)

Reset an initialized permutation iterator to the zero position.

Parameters:
__gc pointer to a permutation iterator structure (EGpermIt_t)

Definition at line 63 of file eg_perm_it.h.


Typedef Documentation

typedef struct EGpermIt_t EGpermIt_t

Structure to store the information relevant to the permutation iterator.


Function Documentation

int main ( int  argc,
char **  argv 
)

main function

Definition at line 39 of file eg_perm_it.ex.c.

References EGlib_info(), EGlib_version(), EGpermItClear, EGpermItGetChange, EGpermItGetTuple, EGpermItInit, EGpermItNext, EGsetLimits(), EGsigSet, prit_usage(), and verbose.

Here is the call graph for this function:

void prit_usage ( char *  program  ) 

given a number, print to standard output a gray code on n bits.

display the usage message for this program

Examples:
eg_perm_it.ex.c.

Definition at line 31 of file eg_perm_it.ex.c.

Referenced by main().