People who like reading this article would absolutely like Knuth's 4A volume of The Art of Computer Programming.
Which discusses Permutations, Combinations, Partitions, boolean tricks and more.
I'm think every so often someone asks if TAOCP is worth reading. Well, yes. It's like this article but denser and more mathematical.
------
I dont think TAOCP covers this superpermutaion problem. Maybe as an exercise though? I've only read the main section, not really dived into the exercise problems yet... Which are substantial and cover more obscure subjects.
- Exercise: Rewrite itertools.product as a generator that yields in a different order than itertools.product; write a different graph traversal that also covers without repetition
>> In mathematics, Hilbert spaces (named after David Hilbert) allow the methods of linear algebra and calculus to be generalized from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise naturally and frequently in mathematics and physics, typically as function spaces. Formally, a Hilbert space is a vector space equipped with an inner product that induces a distance function for which the space is a complete metric space.
>> [...] The inner product between two state vectors is a complex number known as a probability amplitude.
>> In quantum mechanics, energy of a quantum system is described by a self-adjoint (or Hermitian) operator called the Hamiltonian, which acts on the Hilbert space (or a space of wave functions) of the system. If the Hamiltonian is a time-independent operator, emergence probability of the measurement result does not change in time over the evolution of the system. Thus the expectation value of energy is also time independent [If the Hamiltonian is a time-independent operator]
>> [...] the Hilbert curve scheduling method turns a multidimensional task allocation problem into a one-dimensional space filling problem using Hilbert curves, assigning related tasks to locations with higher levels of proximity.[1] Other space filling curves may also be used in various computing applications for similar purposes. [2]
And then fluids.
Computational Fluid Dynamics is still one of the harder problems in classical high performance computing and quantum computing because it is a combinatorically hard problem to model every possible fluid outcome in order to predict the most likely outcome(s).
> For EAs in which, in addition to the offspring, at least the best individual of the parent generation is used to form the subsequent generation (so-called elitist EAs), there is a general proof of convergence under the condition that an optimum exists. Without loss of generality, a maximum search is assumed for the proof: [...]
(Edit: I don't know if it's true but I've heard a story that these sequences were actually used by car thieves to cycle through all N-digit combinations with maximal efficiency. Who says maths isn't useful)
Now, are there any combinatorists here who would be willing to have a private chat with me about something I stumbled upon a few years ago? Almost certainly well known, but I can't find any prior art and I've looked hard.
Eight months ago on HN:
Mystery math whiz and novelist advance permutation problem (quantamagazine.org)
https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-a...
218 points by sashank_1509 8 months ago | hide | past | favorite | 97 comments
https://news.ycombinator.com/item?id=36191831
This new Quanta article:
https://www.quantamagazine.org/unscrambling-the-hidden-secre...
Combinatorics are fun.
People who like reading this article would absolutely like Knuth's 4A volume of The Art of Computer Programming.
Which discusses Permutations, Combinations, Partitions, boolean tricks and more.
I'm think every so often someone asks if TAOCP is worth reading. Well, yes. It's like this article but denser and more mathematical.
------
I dont think TAOCP covers this superpermutaion problem. Maybe as an exercise though? I've only read the main section, not really dived into the exercise problems yet... Which are substantial and cover more obscure subjects.
/? Knuth's 4A volume of The Art of Computer Programming site:github.com : https://www.google.com/search?q=Knuth%27s+4A+volume+of+The+A... :
> Generate {n-tuples, permutations, combinations, partitions, set partitions, trees,} with combinatorial patterns
Combinatorics: https://en.wikipedia.org/wiki/Combinatorics
- Exercise: Permutations [& Combinations]: https://rosettacode.org/wiki/Permutations#Python https://rosettacode.org/wiki/Combinations_and_permutations#P...
- Exercise: Rewrite itertools.product as a generator that yields in a different order than itertools.product; write a different graph traversal that also covers without repetition
- Exercise: The Birthday problem and actual probability of cryptographic hash collision given hash length n: https://en.wikipedia.org/wiki/Birthday_problem
- Exercise: The Gambler's Fallacy: Given a sequence of random values that satisfy many of the tests in e.g. Google/paranoid_crypto.lib.randomness_tests, where would Gambler's Fallacy have caused loss? https://en.wikipedia.org/wiki/Gambler%27s_fallacy https://github.com/google/paranoid_crypto/tree/main/paranoid...
Combinatorics and physics: https://en.wikipedia.org/wiki/Combinatorics_and_physics
/?hnlog Ctrl-f Hilbert :
"Matrices and Graph" https://news.ycombinator.com/item?id=36739579 :
> [ Multigraph, networkx.MultiDiGraph , RDF Linked Data ]
> Tensor product of graphs: https://en.wikipedia.org/wiki/Tensor_product_of_graphs
> Hilbert space: https://en.wikipedia.org/wiki/Hilbert_space :
>> In mathematics, Hilbert spaces (named after David Hilbert) allow the methods of linear algebra and calculus to be generalized from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise naturally and frequently in mathematics and physics, typically as function spaces. Formally, a Hilbert space is a vector space equipped with an inner product that induces a distance function for which the space is a complete metric space.
>> [...] The inner product between two state vectors is a complex number known as a probability amplitude.
Wave interference > Quantum interference: https://en.wikipedia.org/wiki/Wave_interference#Quantum_inte...
EM waves have amplitude in the interval [-1,1] or [-inf, +inf].
With EM waves we typically model constructive interference and destructive interference.
There is also a particle-like phononic quantum wave interpretation of EM waves.
Quantum waves are in the interval [0,1].
Quantum embedding is the process and study of encoding data as wave functions with e.g. phase.
https://news.ycombinator.com/item?id=38255569 :
> How many ways are there to roll a {2, 8, or 6}-sided die with qubits and quantum embedding?
Quantum superposition and combinatorics; why can't the quantum simulator run this code like an actual QC?
"Where does energy go during destructive interference?" (2018) https://news.ycombinator.com/item?id=32421509 :
> From Conservation_of_energy#Quantum_theory https://en.wikipedia.org/wiki/Conservation_of_energy#Quantum... :
>> In quantum mechanics, energy of a quantum system is described by a self-adjoint (or Hermitian) operator called the Hamiltonian, which acts on the Hilbert space (or a space of wave functions) of the system. If the Hamiltonian is a time-independent operator, emergence probability of the measurement result does not change in time over the evolution of the system. Thus the expectation value of energy is also time independent [If the Hamiltonian is a time-independent operator]
{Employee, Conference, Computational resource} Scheduling with priority: https://news.ycombinator.com/item?id=22589911 :
> https://en.wikipedia.org/wiki/Hilbert_curve_scheduling :
>> [...] the Hilbert curve scheduling method turns a multidimensional task allocation problem into a one-dimensional space filling problem using Hilbert curves, assigning related tasks to locations with higher levels of proximity.[1] Other space filling curves may also be used in various computing applications for similar purposes. [2]
And then fluids.
Computational Fluid Dynamics is still one of the harder problems in classical high performance computing and quantum computing because it is a combinatorically hard problem to model every possible fluid outcome in order to predict the most likely outcome(s).
/?hnlog Navier [e Euler, Stokes,] :
- "Deep Learning Poised to ‘Blow Up’ Famed Fluid Equations" https://news.ycombinator.com/item?id=31049608 :
> [awesome-fluid dynamics, jax-cfd,]
And then Evolutionary Algorithms,
- Infinite Monkey Theorem: https://en.wikipedia.org/wiki/Infinite_monkey_theorem
- https://news.ycombinator.com/item?id=39110110#39139198 :
> Holman's "elegant normal form",
Evolutionary Algorithms > Convergence: https://en.wikipedia.org/wiki/Evolutionary_algorithm#Converg... :
> For EAs in which, in addition to the offspring, at least the best individual of the parent generation is used to form the subsequent generation (so-called elitist EAs), there is a general proof of convergence under the condition that an optimum exists. Without loss of generality, a maximum search is assumed for the proof: [...]
The discrete convolution is combinatorial.
Convolution > Discrete convolution: https://en.wikipedia.org/wiki/Convolution#Discrete_convoluti...
Category:Combinatorics: https://en.wikipedia.org/wiki/Category:Combinatorics
⌘F "Haruhi" yields no results. Disappointed that they didn't even name the show!
It's frustrating the article just ends right there. "Then in 2014 someone did even better. The End." What was the new technique?
A very quick skim of the article immediately brought these to mind: https://en.wikipedia.org/wiki/De_Bruijn_sequence
(Edit: I don't know if it's true but I've heard a story that these sequences were actually used by car thieves to cycle through all N-digit combinations with maximal efficiency. Who says maths isn't useful)
Now, are there any combinatorists here who would be willing to have a private chat with me about something I stumbled upon a few years ago? Almost certainly well known, but I can't find any prior art and I've looked hard.
I’m not a combinatorist, but I’m also appalled that two separate Quanta articles didn’t mention De Bruijn sequences.
I see they are trying to spice up math articles, but this is ridiculous !