Depending on the problem, your combinatorial problem might be an interesting fit with Oz, in particular it's finite domain constraint programming. I'll admit it's a bit exotic, though.
I wouldn't use C++, because it won't catch things lack indexing off the end of arrays, and because it won't provide you with a garbage collector. Personally, I'd use, Java, just because that's what I'm familiar with.
I would consider what you are familiar with, what people you want to work with or at least communicate with are familiar with, and what libraries are available that you might want to use. This might include things like I/O or graphics libraries for post-processing results, as well as specialiased combinatorial algorithms. You might also look for profiling tools, so you can see where your algorithm is spending all its time.
I think that you are going to find that most of the popular very high level languages that are ideal for prototyping are 'weakly typed'.
Also, when I unit test, it's almost never to make sure that things are of the right type. This is very seldom as big a problem as it's made out to be. You should unit test to ensure freedom of the algorithm from bugs of any cause.
You mentioned python, so I will recommend that, not being familiar with haskell myself. Python has Numpy and integrates very well with C. It also has the itertools module in stdlib which is very nice for combinatorial work (judiciously applied, It can outperform slightly better than mediocre C). I'm currently working on a similar project and I prototyped it out with python. I'm currently in the process of translating most of it to C. This is a nice process because I already have a python implementation of every algorithm so once I get my C wrapped for python, I can test the two off against each other to make sure that they give identical output on identical input. So because I built a prototype in python, I get both a very cheap testing framework for my application and a python module written in C.
Plus I've already found optimal (or at least sufficient) algorithms and if a new one occurs to me, I can quickly modify the python in a different branch to test it for efficiency.
Whatever language you choose, consider making sure that it integrates well with your ultimate target language to take advantage of similar perks.
I haven't used Python, and I've only used Haskell a little, for exactly the purpose you describe -- prototyping things. The thing to watch out for there is not the slowdown that laziness gives you, but rather the fact that seemingly constant-space algorithms can have space leaks that consume all available memory with thunks representing unevaluated chunks of code. Space leaks are hard to see.
Of course, you can worry about them and scour your program looking for them, exterminating them with seq and other forms of ugliness... But the point of using a prototyping language is to avoid all those headaches.
If you're playing with problem sizes so small that it doesn't matter if a thunk is created in memory for every evaluation step in your program from beginning to end, then I could recommend Haskell.
C# 4.0
It has almost all the features you require.
NOTE: I myself would go with Python and write some modules in C++. ;)
I would suggest to give D a shot. It is close to C++, but much easier to reason about and without all the ugly warts. If you're thinking about writing the final implementation in C++, it's much easier to translate D to C++ as Python, and additionally you have the option to stay with D, as the performance is on par with C++.
While i'd encourage you to learn more languages, if your goal is to prototype this problem as quickly as possible i'd stick with C++ (as you seem to be proficient in it already).
while other languages are probably better for prototyping in general if you only know C++ now, you will probably have a resonably large learning curve which will slow you down enough that you lose its advantage for this project at least (especially if you are looking at major paradigm change as well).
on the other hand if this is actually more about broadening your knowledge for the future then pretty much any of the scripting languages will do.
I'm a Haskell programmer for more than 7 years and I haven't used any other language for serious work since. My recommendation is, of course, Haskell. :-)
In my experience, here is what you can expect of Haskell:
:
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)
I don't think it's possible to back up these experiences with anything other than experience; so, you have to take my word for it.
Several experience reports have been published formally, see also the Haskell in Industry page. I found Haskell vs. Ada vs. C++ vs. Awk vs. ... An Experiment in Software Prototyping Productivity [ps] to be particularly enlightening.
Haskell can really shine if you can express the problem domain as an "embedded domain specific language" (eDSL). This is actually just a function library with pretensions, but the trick is to define an underlying abstraction and functions to manipulate it. Its difficult to explain in more concrete terms without understanding your domain better, but I expect you want to give an underlying combinatorial algorithm some hints about which parts of the problem to tackle first, and how to identify promising partial solutions.
Start by taking a look at the list monad. If your problem is not too complex then this might actually be all you need. For more, look at this page for ideas on how to add backtracking and pruning.