find every 3-subsets adding up to 9 #Ashish

Q: You have 9 poker cards, numbered 1 to 9. Given two integers SUM (for example 11) and COUNT (for example, 3), construct every combination of 3 cards, who add up to the target 11.

Within each combination, if we need to generate each permutation, it’s as simple as calling next_permutation() within an array (which is a combination).

You can only choose each card 0 or 1 time, i.e. no redraw.

I used to feel this was dynamic programming. Now I feel we have no choice but iterate over all combinations. We have an algo to generate ascending combinations. We can stored them in mini arrays, each one is ascending. We could use binary search in each mini-array.

https://github.com/tiger40490/repo1/blob/cpp1/cpp/array/sizeN-subset_TargetSum_Ashish.cpp is a very short recursive solution by my friend CSY.

//There are N distinct poker cards numbered 1 to N. Find all combinations
//of C cards such that each combo adds up to the same given Target
//
//Based on https://bintanvictor.wordpress.com/2017/11/08/generate-next_combo3-boys-out5-recursive/
//
//Note some range of the generated sequence is ascending, permitting
//binary search like lower_bound, but it's not easy to tweak the algo
//to skip ahead. There's no random access iterator here!
#include <iostream>
#include <sstream>
#include <deque>
#include <iomanip> //setw
#include <algorithm>  //sort
#include <assert.h>
//#define DEBUG
using namespace std;
size_t calls=0, combos=0;
size_t const C=3; //how many in each combination
size_t const Target=12;
deque<int> pool{1,3,4,5,8};
deque<int> prefix;

template<typename T> void dumpDeque(deque<T> const & p, string const & headline){
  cout<<"-- "<<headline<<" -- size = "<<p.size()<<endl;
  for(int i=0; i<p.size(); ++i) cout<<setw(5)<<p[i];
  cout<<endl;
}
template<typename T> int showCombo(deque<T> const * p){
  ++ combos;
  size_t sum = 0;
  stringstream ss;
  for(int i=0; i<p->size(); ++i){
        ss<<setw(5)<<(*p)[i];
        sum+= (*p)[i];
  }
  static string last;
  string combo=ss.str();
  cout<<"combo: "<<combo;
  if (sum == Target) cout<<" <- Hit!";
  cout<<endl;
  assert(last <= combo && "should be ascending");
  last = combo;
}

template<typename T> int recurs(){
  ++calls;
#ifdef DEBUG
  cout<<"-------------\nentering "; dumpDeque(prefix, "prefix"); dumpDeque(pool, "pool");
#endif
  if (prefix.size() == C) return showCombo(&prefix); //prefix alone is the combo
  if (pool.empty()) return 0;
  T poolhead = pool.front(); pool.pop_front();

  prefix.push_back(poolhead); //add poolhead to prefix

  //this 1st recursive function call starts a rather deep call stack and prints
  //all combinations that start with the given (new longer) prefix
  recurs<T>();//use the longer prefix and the shorter pool

  prefix.pop_back();//restore prefix
  recurs<T>();
  pool.push_front(poolhead); //restore pool, needed by the 2nd call in the parent stack
#ifdef DEBUG
  cout<<"^^^^^^ restored before returning "; dumpDeque(prefix, "prefix"); dumpDeque(pool, "pool");
#endif
}

int main() {
  assert(C <= pool.size());
  sort(pool.begin(), pool.end());
  recurs<int>();
  cout<<calls<<"  calls to the recursive function to generate "<<combos<<endl;
}
Advertisements

mv-semantic: %%Lesson #1

#9 std::move()
#8 STL containers using mv-semantic — confusing if we don’t have a firm grounding on …

#7 mv ctor and mv assignment — all the fine details would be poorly understood if we don’t have a grip on …

#5 RVR — is a non-trivial feature by itself. First, we really need to compare…

#3 rval expression vs lval expression — but the “expression” bit is confusing!

#1 lval expression vs lval variable vs objects in a program
This is fundamental concept.

RVR – exclusively used as function parameter@@

RVR – exclusively(?) used as function parameter

There could be tutorials showing other usages, like a regular variable, but i don’t see any reason. I only understand the motivation for
– move-ctor/move-assignment and
– insertions like push_back()

When there’s a function (usually a big4) taking a RVR param, there’s usually a “traditional” overload without RVR, so compiler can choose based on the argument:
* if arg is an rval expression then choose the RVR version [1]
* otherwise, default to the traditional

[1] std::move(myVar) would cast myVar into an rval expression. This is kind of adapter between the 2 overloads.

In some cases, there exists only the RVR version, perhaps because copy is prohibited… like in a class holding a FILE pointer?

Microsoft COM – a few keywords

“COM library” vs “type library”???

I suspect most code (whether people mention COM or not) written before dotnet are probably technically COM code???

— dotnet without the dotnet context —

Client/server — A COM client is whatever code or object that gets a pointer to a COM server and uses its services. A COM server is any object that provides services to clients. In-process servers are implemented in a dynamic linked library (DLL), and out-of-process servers are implemented in an executable file (EXE). Out-of-process servers can reside either on the local computer or on a remote computer.


Registry — COM types are usually listed by GUIDs in the registry, though some COM types are RegFree

DLL — COM components are usually implemented in DLL files, and registration allows only a single version of a DLL. Dotnet classes also exist in DLL or EXE files.


MS-Office – For example COM allows Word documents to dynamically link to data in Excel spreadsheets
Bindings — COM interfaces have bindings in several languages, such as C, C++, Visual Basic

ActiveX – is part of COM


— Excel Addin —
All COM Add-ins must implement each of the five methods of this interface: OnConnection, OnStartupComplete, OnAddinsUpdate, OnBeginShutDown, and OnDisconnection.

joint prob – jargon, …

Relevance –
– I feel conditional prob is based on joint prob
– conditional expn is based on joint prob

I feel one *extensible* example would be poker cards with 2 colors, 4 shapes, 13 values (based on how many “points”).

Important – variance of X+Y. http://www.math.cornell.edu/~back/m171/var_sum.pdf is a simple proof in discrete case.

Somewhat important – X*Y