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

# include "knapsack_random.h"

/******************************************************************************/

void knapsack_random ( int n, int *s )

/******************************************************************************/
/*
  Purpose:

    knapsack_random() returns a random possible solution of a knapsack problem.

  Discussion:

    The subset is represented as a vector of binary digits.

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    29 November 2024

  Author:

    John Burkardt

  Input:

    integer n: the total number of items in the set.

  Output:

    integer s[n]: a subset.  Item i is in the subset if s[i] = 1.
*/
{
  subset_random ( n, s );

  return;
}
/******************************************************************************/

void subset_next ( int n, int *s )

/******************************************************************************/
/*
  Purpose:

    subset_next() returns the next subset of n items.

  Discussion:

    The subset is represented as a vector of binary digits.
    The subsets are listed in numerical order.
    After the last subset is returned, the sequence begins again at 0.

  Example:

    [ 0, 0, 0 ]
    [ 0, 0, 1 ]
    [ 0, 1, 0 ]
    [ 0, 1, 1 ]
    [ 1, 0, 0 ]
    [ 1, 0, 1 ]
    [ 1, 1, 0 ]
    [ 1, 1, 1 ]

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    29 November 2024

  Author:

    John Burkardt

  Input:

    integer n: the number of items in the set.

    integer s[n]: the current subset.

  Output:

    integer s[n]: the next subset.
*/
{
  int i;
/*
  Starting at the last index, add 1, and if necessary, carry to the left.
*/
  for ( i = n - 1; 0 <= i; i-- )
  {
    if ( s[i] == 0 )
    {
      s[i] = 1;
      break;
    }
    else
    {
      s[i] = 0;
    }

  }

  return;
}
/******************************************************************************/

void subset_random ( int n, int *s )

/******************************************************************************/
/*
  Purpose:

    subset_random() returns a random subset of n items.

  Discussion:

    The subset is represented as a vector of binary digits.

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    29 November 2024

  Author:

    John Burkardt

  Input:

    integer n: the total number of items in the set.

  Output:

    integer s[n]: a subset.  Item i is in the subset if s[i] = 1.
*/
{
  int i;
  long int r;

  for ( i = 0; i < n; i++ )
  {
    r = rand ( );
    s[i] = ( r % 2 );
  }

  return;
}
/******************************************************************************/

int subset_to_rank ( int n, int *s )

/******************************************************************************/
/*
  Purpose:

    subset_to_rank() returns the rank of a subset().

  Discussion:

    The subset is described by a binary vector of n digits.
    The units digit is the last one.
    Reading from right to left, we add selected powers of 2.

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    29 November 2024

  Author:

    John Burkardt

  Input:

    integer n: the number of items in the set.

    integer s[n]: the current subset.

  Output:

    int subset_to_rank: the rank of the subset.
*/
{
  int i;
  int index;
  int power2;

  index = 0;
  power2 = 1;
  for ( i = n - 1; 0 <= i; i-- )
  {
    index = index + s[i] * power2;
    power2 = power2 * 2;
  }

  return index;
}