# include <cstdlib>

using namespace std;

# include "knapsack_random.hpp"

//****************************************************************************80

void knapsack_random ( int n, int *s )

//****************************************************************************80
//
//  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:
//
//    30 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;
}
//****************************************************************************80

void subset_next ( int n, int *s )

//****************************************************************************80
//
//  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:
//
//    30 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;
}
//****************************************************************************80

void subset_random ( int n, int *s )

//****************************************************************************80
//
//  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:
//
//    30 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;
}
//****************************************************************************80

int subset_to_rank ( int n, int *s )

//****************************************************************************80
//
//  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:
//
//    30 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;
}