3 ms·

Unscrambling the hidden secrets of superpermutations

40 points by RafelMri 3y ago

saagarjha 3y ago
⌘F "Haruhi" yields no results. Disappointed that they didn't even name the show!
- plagiarist 3y ago
  It's frustrating the article just ends right there. "Then in 2014 someone did even better. The End." What was the new technique?
defrost 3y ago
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-anonymous-math-whiz-advance-permutation-problem-20181105/ 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 https://news.ycombinator.com/item?id=36191831 This new Quanta article: https://www.quantamagazine.org/unscrambling-the-hidden-secrets-of-superpermutations-20190116/ https://www.quantamagazine.org/unscrambling-the-hidden-secre...
dragontamer 3y ago
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.
- westurner 3y ago
  /? 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+Art+of+Computer+Programming+site%3Agithub.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 https://en.wikipedia.org/wiki/Combinatorics - Exercise: Permutations [& Combinations]: https://rosettacode.org/wiki/Permutations#Python https://rosettacode.org/wiki/Permutations#Python https://rosettacode.org/wiki/Combinations_and_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 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://en.wikipedia.org/wiki/Gambler%27s_fallacy https://github.com/google/paranoid_crypto/tree/main/paranoid_crypto/lib/randomness_tests https://github.com/google/paranoid_crypto/tree/main/paranoid... Combinatorics and physics: https://en.wikipedia.org/wiki/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 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 https://en.wikipedia.org/wiki/Tensor_product_of_graphs > Hilbert space: https://en.wikipedia.org/wiki/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_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 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 https://news.ycombinator.com/item?id=32421509 : > From Conservation_of_energy#Quantum_theory https://en.wikipedia.org/wiki/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://news.ycombinator.com/item?id=22589911 : > https://en.wikipedia.org/wiki/Hilbert_curve_scheduling 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 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://en.wikipedia.org/wiki/Infinite_monkey_theorem - https://news.ycombinator.com/item?id=39110110#39139198 https://news.ycombinator.com/item?id=39110110#39139198 : > Holman's "elegant normal form", Evolutionary Algorithms > Convergence: https://en.wikipedia.org/wiki/Evolutionary_algorithm#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: [...]
_a_a_a_ 3y ago
A very quick skim of the article immediately brought these to mind: https://en.wikipedia.org/wiki/De_Bruijn_sequence 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.
- BobbyTables2 3y ago
  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 !

40 points by RafelMri 3y ago

saagarjha 3y ago

⌘F "Haruhi" yields no results. Disappointed that they didn't even name the show!

plagiarist 3y ago
It's frustrating the article just ends right there. "Then in 2014 someone did even better. The End." What was the new technique?

defrost 3y ago

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-anonymous-math-whiz-advance-permutation-problem-20181105/ 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 https://news.ycombinator.com/item?id=36191831 This new Quanta article: https://www.quantamagazine.org/unscrambling-the-hidden-secrets-of-superpermutations-20190116/ https://www.quantamagazine.org/unscrambling-the-hidden-secre...

dragontamer 3y ago

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.

westurner 3y ago
/? 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+Art+of+Computer+Programming+site%3Agithub.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 https://en.wikipedia.org/wiki/Combinatorics - Exercise: Permutations [& Combinations]: https://rosettacode.org/wiki/Permutations#Python https://rosettacode.org/wiki/Permutations#Python https://rosettacode.org/wiki/Combinations_and_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 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://en.wikipedia.org/wiki/Gambler%27s_fallacy https://github.com/google/paranoid_crypto/tree/main/paranoid_crypto/lib/randomness_tests https://github.com/google/paranoid_crypto/tree/main/paranoid... Combinatorics and physics: https://en.wikipedia.org/wiki/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 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 https://en.wikipedia.org/wiki/Tensor_product_of_graphs > Hilbert space: https://en.wikipedia.org/wiki/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_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 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 https://news.ycombinator.com/item?id=32421509 : > From Conservation_of_energy#Quantum_theory https://en.wikipedia.org/wiki/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://news.ycombinator.com/item?id=22589911 : > https://en.wikipedia.org/wiki/Hilbert_curve_scheduling 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 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://en.wikipedia.org/wiki/Infinite_monkey_theorem - https://news.ycombinator.com/item?id=39110110#39139198 https://news.ycombinator.com/item?id=39110110#39139198 : > Holman's "elegant normal form", Evolutionary Algorithms > Convergence: https://en.wikipedia.org/wiki/Evolutionary_algorithm#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: [...]

_a_a_a_ 3y ago

A very quick skim of the article immediately brought these to mind: https://en.wikipedia.org/wiki/De_Bruijn_sequence 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.

BobbyTables2 3y ago
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 !