Using pointers to find a subset of size k of a linked list of size n

[arielle]

I am trying to find a subset of a linked list using pointers. I have tried using recursion to do it, but it's not really working.

For example, if I have a linked list of size 5: h -> 1 -> 2 -> 3 -> 4
And I want to find all possible subsets of size 4 with h always being the first node and creating a new linked list every time and storing those lists, how should I do it?

In this case, all the possible subsets would be:
h -> 1 -> 2 -> 3
h -> 1 -> 2 -> 4
h -> 1 -> 3 -> 4
h -> 2 -> 3 -> 4

[lastchance]

Well, you could do it purely from the "indices" - either means counting through the linked list each time, or just putting the data into a different container.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
   const int MAXIMUM = 4, NUM_REQUIRED = 3;
   vector< vector<int> > sequences;
   for ( int i = 1; i <= 9; i++ ) sequences.push_back( { i } );

   for ( int n = 2; n <= NUM_REQUIRED; n++ )
   {
      vector< vector<int> > old = sequences;
      sequences.clear();
      for ( const vector<int> &S : old )
      {
         for ( int d = S.back() + 1; d <= MAXIMUM; d++ ) { sequences.push_back( S ); sequences.back().push_back( d ); }
      }
   }

   for ( auto &S : sequences )
   {
      cout << 'h';
      for ( int i : S ) cout << " -> " << i;
      cout << '\n';
   }
}

h -> 1 -> 2 -> 3
h -> 1 -> 2 -> 4
h -> 1 -> 3 -> 4
h -> 2 -> 3 -> 4

[arielle]

Thank you for your reply! But is there a way I could do it without using vectors? As I haven't learnt vectors yet.

[seeplus]

Basically just replace vector with list:

#include <iostream>
#include <list>
using namespace std;

int main() {
	constexpr int MAXIMUM {4}, NUM_REQUIRED {3};
	list<list<int>> sequences;

	for (int i = 1; i <= 9; ++i)
		sequences.push_back({i});

	for (int n = 2; n <= NUM_REQUIRED; ++n) {
		const auto old {sequences};

		sequences.clear();

		for (const auto& S : old)
			for (int d = S.back() + 1; d <= MAXIMUM; ++d) {
				sequences.push_back(S);
				sequences.back().push_back(d);
			}
	}

	for (auto& S : sequences) {
		cout << 'h';

		for (int i : S)
			cout << " -> " << i;

		cout << '\n';
	}
}

[lastchance]

#include <iostream>
#include <list>
using namespace std;

int main()
{
   const int NUM_REQUIRED = 4;
   list<int> original = { 0, 10, 20, 30, 40 };

   auto it = original.begin();                  // say
   list< list<int> > sequences = { { *it } };
   
   int left = original.size() - 1;
   for ( it++; it != original.end(); it++, left-- )
   {
      list< list<int> > added;      
      for ( auto &S : sequences )
      {
         if ( S.size()        < NUM_REQUIRED ) { added.push_back( S ); added.back().push_back( *it ); }  // sequence WITH    element (if possible)
         if ( S.size() + left > NUM_REQUIRED )   added.push_back( S );                                   // sequence WITHOUT element (if possible)
      }
      sequences = added;
   }

   for ( auto &S : sequences )
   {
      for ( auto e : S ) cout << e << "  ";
      cout << '\n';
   }
}

0  10  20  30  
0  10  20  40  
0  10  30  40  
0  20  30  40