I got hit by an interesting problem of “Zebra Puzzle” the other day. It is a well known logic puzzle believed to be first invented by Albert Einstein.
The question here is, how do we use our favorite programming language to solve this problem?
The first obstacle I found is that we need to generate all permutation of given list. Say if we have [1,2,3], we have a total of 3! = 6 which are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. I couldn’t find simple Javascript code for this so I ended up writing one. Reinventing the wheel is fun, isn’t it? :))
Wikipedia suggests the following algorithm for generating all permutation systematically.
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
- Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
- Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
- Swap a[k] with a[l].
- Reverse the sequence from a[k + 1] up to and including the final element a[n].
Here is my PermutationGenerator module implemented in Javascript.
/////////////////////////////////////////////
// Permutation Generator
// - generate all permutation of given string
// array
// - Natthawut Kulnirundorn <m3rlinez at email by google>
// http://www.solidskill.net 10 July 2011
/////////////////////////////////////////////
var PermutationGenerator = (function () {
var self = {};
// Get start sequence of given array
self.getStartSequence = function (list) {
return list.slice(0).sort();
};
// Get next sequence from given array
// Ref: http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
self.getNextSequence = function (list) {
// Make clone
var a = list.slice(0);
//The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
// 1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
var k = -1;
for (var i = 0; i < a.length - 1; ++i) {
if (a[i] < a[i + 1]) { k = i; }
}
if (k == -1) return null; // means this is the last one
// 2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
var l = -1;
for (var i = 0; i < a.length; ++i) {
if (a[k] < a[i]) { l = i };
}
if (l == -1) return null; // impossible
// 3. Swap a[k] with a[l].
var tmp = a[k]; a[k] = a[l]; a[l] = tmp;
// 4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
var next = a.slice(0, k + 1).concat(a.slice(k + 1).reverse());
return next;
};
return self;
} ());
/////////////////////////////////////////////
// Test Cases
/////////////////////////////////////////////
var PermutationGeneratorTest = (function () {
var self = {};
function getStartSequence_Test1() {
var a = ['red', 'white', 'green', 'yellow', 'blue'];
var res = PermutationGenerator.getStartSequence(a);
log('input = ' + a);
log('output = ' + res);
}
function generateSequence(list) {
var current = PermutationGenerator.getStartSequence(list);
var count = 1;
log('start = ' + current);
while (true) {
current = PermutationGenerator.getNextSequence(current);
if (current == null) { break; }
log('next' + (++count) + ' = ' + current);
}
}
function getNextSequence_TestNormal() {
generateSequence(['English', 'Spanish', 'Japanese']);
}
function getNextSequence_TestEmpty() {
generateSequence([]);
}
function getNextSequence_TestRepeat() {
generateSequence(['gant', 'gant', 'korkore', 'jan']);
}
self.runTests = function () {
log("=== getStartSequence 1 ===");
getStartSequence_Test1();
log("=== getNextSequence Normal ===");
getNextSequence_TestNormal();
log("=== getNextSequence Empty ===");
getNextSequence_TestEmpty();
log("=== getNextSequence Repeat ===");
getNextSequence_TestRepeat();
};
return self;
} ());
I have put the working example on http://www.solidskill.net/ZebraPuzzle.htm. There are other parts of code that search through the solution space, setup the constraints for Zebra puzzle. But they are not discussed here.
There are some things to note about this implementation though. First, it is not very efficient. You can see in the getNextSequence(..) loop that there are loops used to search for k and l that satisfy the conditions.
Second, there could be problem with list of integers. The Array.sort() in Javascript sort using string interpretation by default. So [4, –1, 100, 500].sort() would return [-1, 100, 4, 500] instead of expected [-1, 4, 100, 500]. One must give Array.sort() function the comparer in order to properly sort list of integer. I design this module to work with list of strings initially.
Hope this helps those who are looking for permutation generation code.
141 comments:
hey this looks useful! I have a few short lists to premutate so performance may not be an issue.
can I use it under the MIT license?
Really Good blog post.provided a helpful programs for generating permutation with javascript. keep updating...
Digital marketing company in Chennai
https://newyear2019love.com/ wishes for new year
Black Friday 2018
Black Friday 2018
2018 Black Friday
Black Friday 2018 Deals
Black Friday 2018 Online Deals
Black Friday Walmart
Black Friday Online Deals
Black Friday 2018 Deals Online
PSL T20 Live streaming for all matches
https://happyvalentinesday2019.net/ best quotes for lover
Nice thoughts with great helping content. I have also been seeking such thoughfull content to learn and appy in the life. We have also created such type of content on our site. You can refer out site for more ideas.
Happy New Year 2019 Wishes Messages Sms in Bengali
Merry Christmas 2018 SMS, Wishes, Messages, Greetings in Bengali
Merry Christmas 2018 Wishes Messages in Marathi,funny christmas text sms
https://teacherappreciationweekideas.com best way to know
best way to know
pip camera new version 2019
Happy New Year 2019 Sms & Wishes to your family friends - Hamariweb.com has a great collection of New Year Wishes, New Year Sms quotes, & greeting in in
Happy New Year 2019 Wishes For Friends
https://newyear2019s.com/
best way to know
Sketch Maker new version 2019
Free download valentine's day ecards
This is certainly additionally an exceedingly wonderful offer everyone truly qualified on the lookout with. It's always not likely everyday there is chances read a little something. extremely well written article as . I will be sure to and return to read more of your useful information. Thanks for the post. I’ll certainly comeback.
valentine's day movie quotes movie funny quotes
This article is actually a nice one it helps new internet viewers, who are wishing in favor of blogging. For more information https://latestgovtjobs2019.in latest news and I absolutely love your blog and find almost all of your post’s to be just what I’m looking for. Does one offer guest writers to write content to suit your needs? https://upboard10thresult2019.com
Thank you for your post, I’ve been trying sarkari resultor a while but I never seem to get jobnotifys.in there! Appreciate it. :) I liked it
Norton antivirus phone number
McAfee support number
Malwarebytes customer support number
Hp printer support chat
Canon printer customer support number
He tuhinga tino pai. Mauruuru, whakawhetai koe
lưới chống chuột
cửa lưới dạng xếp
cửa lưới tự cuốn
cửa lưới chống muỗi
Kursus Indonesia
Kursus Indonesia
Kursus Indonesia
Konslet
Memory Card
Konektor Charger
Firmware Android
Imei Null
Octoplus Samsung
Baterai Tanam
Service Electronic
Handphone Error
ZTE Huawei
LCD Warna Warni
Freelance
Xiaomi
Port USB
Komponen HP
Cara Menghidupkan HP Mati Total Baterai Tanam
Macam Macam IC
Cara Memperbaiki LCD
Tombol Volume
Lembaga Kursus Terbaik Indonesia
Imei
Baterai
Thanks for sharing this article with us.
Check out the board result of class 10th and 12th exam of all major boards.
Also, check cbse nic result 2019 of board exam for 10th and 12th Class which will be declared very soon.
We are offering Best Cleaning Service in Dubai Sharjah Ajman
Call Now : 056 16 15 616
https://plutoniccleaningandtech.com
Sofa Cleaning Services in Dubai
General Cleaning Services Dubai
Sofa General Cleaning Services Dubai
Sofa Deep Cleaning Services Dubais
Sofa Shampooing Cleaning Services Dubai
Sofa Shampooing Cleaning Services Dubai
Sofa Steam Cleaning Dubai
Office Sofa Cleaning Services Dubai
House Sofa Cleaning Services Dubai
Very nice blgo, you are sharing very nice information,
if someone here looking for awesome stories to read kindly visit my website DelhiMeraki
This post is very useful info. Great information about the Javascript.we are the best digital marketing company in Chennai and also the best website designing company in Chennai.
Nice article with lots of great information. Here are best site to Buy Real Instagram Followers Paytm and Paypal and grow instagram, facebook, youtube social media from targeted audience.
Keep posting more article : SNK Creation
My all time fav post, thanks for sharing dear. Do you need high profile and celebrities instagram followers and likes than here are one of world best site to Buy instagram followers India
I always look your website for new update. Go ahead….
SNK Social Fame
Cryptocurrency Exchange Software Development
Binance Clone Script
DeFi Development Company
DeFi Staking Development
Uniswap Clone
PancakeSwap Clone Script
Binance Smart Chain Development
Cryptocurrency Exchange Script
Uniswap Clone Script
Binance Clone Script
1Inch Exchange Clone Script
White Label Crypto Exchange
Binance Smart Chain Token Development
Cryptocurrency Exchange Development Company
TokenMint Clone Script
Bep20 Token Development Company
Ethereum Exchange Script
I read this article. I think You put a great deal of exertion to make this article.
buy instagram likes
high quality smm service provider
We Provide High Quality Smm Service Buy Smm Services
BEP20 Token Development Company
NFT Marketplace Development Company
Blockchain Development Company
NFT Marketplace Clone Script Providers
On demand app development company
Pancakeswap Clone Script
Binance Clone Script
Nice informative written!
BEP20 token development company
NFT Marketplace Development
A good article
great insight
Thanks for sharing valuable information, I really very impressed with your blog.
Ecommerce Web Development Company In Chennai
Ecommerce Web Development In Chennai
Pancakeswap Clone Script
Pancakeswap Clone Software
Pancakeswap Clone Development
Pantherswap Clone Script
Pantherswap Clone Software
Pantherswap Clone Development
Decentralized exchange script
Decentralized exchange software
Binance Clone Script
Cryptocurrency Exchange Script
P2P Cryptocurrency Exchange Script
BEP20 token generator
blockchainx
Uniswap Clone Script
Thanks,
GloriaFood Alternative Solution
Thanks for this amazing post.
Visit:-
considir
bitrated
hydroshare.org
emdr-mn
ebluejay
Axie Infinity Clone Script
Uniswap Clone Script
Binance Clone Script
PancakeSwap Clone Script
NFT Marketplace Development
Maticz, one of the globally leading Solana Blockchain development companies, provides you with highly refined and promising services. Here at maticz we offer you Solana-based NFT,NFT marketplaces, DApps and smart contracts services.
Maticz is the best place to take your crypto business to the next level, Connect with our experts now.
solana blockchain development company
Crypto Staking
Uniswap clone script
NFT Marketplace Development Company
PancakeSwap Clone Script
DeFi Development Services
Thank you share the gratefulness post
Axie infinity clone script
Thank you for sharing this valuable post!
- BEP20 token generator
NFT Marketplace Development Company
White Label NFT Marketplace Development Company
Opensea Clone Script
Binance Clone Software
Pancakeswap Clone
BEP20 Token Development
BSC NFT Marketplace
NFT Development company
IDO Development
BSC Smart Contract Development
NFT Smart Contract Development
Crypto Exchange Clone Script
Defi development company
Trust wallet clone
Uniswap clone
NFT Gaming Platform Development
Uniswap Clone Script
Pancakeswap Clone Script
DeFi Development Company
Create NFT Marketplace
White Label Crypto Exchange Software
Token Development Company
NFT Marketplace App Development
Binance NFT Marketplace Clone script
CryptoPunks Clone Script
Create BEP20 Token
NFT Token Development
Safemoon Clone Script
CryptoPunks Clone Script
Axie Infinity Clone Script
Polkawar Clone Script
TinyHero Clone Script
Cryptozoon Clone Script
Cryptoblades Clone Script
ZedRun Clone Script
FoxyNFT Game Clone
Decentraland Clone Script
Sorare Clone Script
Valuable Post! thank You
Cointool App Clone Script |
Zed Run Clone Script
Token Generator Platform Development Company |
Crypto Punks Clone Script |
Zed Run Clone Script
Cointool App Clone Script |
Sorare Clone Script
Token Generator Platform Development Company |
Crypto Punks Clone Script |
Metaverse NFT Marketplace Development Company
The ADA's digital marketing course contains exceptionally compelling digital marketing training that will assist you with finding modern strategies for brand advancement. We are satisfied to acquaint you with a legitimate computerized advertising school that offers online business courses to assist you with propelling your vocation and business. We've set up a norm for giving the best Digital Marketing Company in Amritsar. We need to direct your vocation in the appropriate way, in light of our set up history of various fruitful voyages. The methods we instruct are altogether founded on true undertakings. We work with students to assist them with further developing their reasoning abilities and widen their inventiveness.
Thanks for sharing this Fantastic post!
Axie Infinity Clone Script
Thanks for sharing useful information. Keep it up
OpenSea Clone |
Axie Infinity Clone |
Zed Run Clone
Decentraland Clone
Cointool App Clone |
Nice Blog
Zed run clone script
Token Development |
Ethereum Token Development Company |
NFT Token Development Company |
DeFi Token Development Company |
Smart Contract Development Company |
BEP20 Token Development Company |
This is a nice Post!
TinyHero Clone |
OpenSea Clone |
Axie Infinity Clone |
Zed Run Clone
Cointool App Clone |
Excellent Post!
OpenSea Clone |
NBA Top Shot Clone |
Sorare Clone |
Cryptopunks Clone |
Axie Infinity Clone |
Zed Run Clone |
Amazing blog post!
OpenSea Clone Script
Opensea clone script
Axie infinity clone script
Rarible clone script
Zed run clone script
Cryptopunks clone script
cryptocurrency exchange software development
cryptocurrency exchange software development company
NFT Gaming Platform Development
Uniswap Clone Script
Pancakeswap Clone Script
Decentraland Clone Script
Axie Infinity Clone Script
DeFi Development Company
Sandbox Clone Script
Opensea Clone Script
Decentralized Exchange Script
DeFi Development Services
Amazing post, thanks for sharing
Opensea clone script
Decentraland Clone Script
It is very useful information, Thank you for this. If you are looking for an NFT Token Development company, then I want to suggest Zeligz Web Store. It provides the best NFT development services in India. It provides all functions that help to develop your business.
NFT Marketplace Development Company
Decentraland clone script
Opensea clone script
Rarible clone script
Axie infinity clone script
Zed run clone script
Cryptocurrencies are one of the hot trends in the current crypto world. So launching a crypto-related business will be a great revenue-generating business in the present crypto world.
dxsale clone
dxsale clone script
Rarible clone script
Opensea clone script
Decentraland clone script
Axie infinity clone script
Zed run clone script
NFT Game Development Company
NFT Marketplace Development Company
Token Development |
Token Development Services
Cryptocurrency Development Services
ERC20 Token Development Company |
ICO Development Company |
White Paper Writing Services |
Sandbox Clone Script | Sandbox Clone Development | Create NFT Marketplace like Sandbox
Metaverse NFT Marketplace Development | Metaverse Development company
Solsea clone Script | Solsea clone Development | Create NFT Marketplace like Solsea
Solanart clone Script | Solanart clone Development | Create NFT Marketplace like solana
F1 Delta Time Clone Script | F1 Delta Time Clone Development | Create Digital Car Race Game
Nice article to read!
Trust Wallet Clone Script
Cryptocurrency Wallet Company
Amazing post! Thanks for sharing
NFT Marketplace Development Company
Gamefi clone script
Opensea clone script
Axie infinity clone script
Decentraland clone script
Rarible clone script
Zed run clone script
Pancakeswap clone script
GameFi clone script
Sandbox clone script
NFT Marketplace Development Company
Axie infinity clone script
Zed run clone script
Opensea clone script
Blockchain Development Services
Blockchain Firm provides reliable and custom blockchain development services for large enterprises and medium business organizations
Blockchain development services
This article is fully fantastic and informative! It contains a lot of useful information that can be helpful in some or the other way. Keep updating the blog like this, I look forward to so many more interesting things. Thank you very much for all the details.
Solana Software Devlopment Company
kraken clone script
NFT Game Development Company
Axie Infinity Clone Script
Zed run clone script
Cryptokitties clone script
Trustwallet clone script
DeFi Development
Pancakeswap Clone script
NFT Marketplace Development Company
Metaverse Development Company
white Label Crypto Exchange Software
BEP20 Token Development
NFT Minting Platform Development Company
Solana Token Development Company
ERC20 Token Development Company
Smart Contract Development Company
NFT Token Development Company
Polygon Token Development Company
DeFi Development Company
Pancakeswap Clone Script
DeFi Staking Platform Development
Trustwallet Clone App
Excellent post, thanks for sharing
Cryptocurrency Exchange Software Development
NFT Marketplace Development Company
Thanks you for sharing this unique useful information content with us. Really awesome work. keep on blogging
Teen Patti Game Development Company
Pancakeswap clone script
Wazirx clone script
Cryptocurrency exchange development company
LocalBitcoins clone script
NFT Marketplace Development Company
Binance Clone Script
NFT Development Company
BEP20 Token Development Services
BEP20 Token Development agency
BlockchainX's expert developers have answers for you with state of the art Erc20 token generator. Give your Dapps the power of ethereum erc20 token development company based and integrate secured crypto payment systems.
Launch an NFT marketplace that supports art, music, real-estate or GameFi with our NFT Marketplace Development Services. Build robust blockchain solutions with an industry-leading NFT Marketplace Development Company. Build enterprise blockchain solutions with Corda blockchain development company. Hire expert Corda blockchain developers.https://www.blockchainx.tech/nft-marketplace-development
Well-written and informative article. Thanks! for sharing this article with us. Do you want to launch your own NFT Marketplace like Rarible? Explore here --> Rarible Clone Script
NFT Marketplace Development Company
Opensea clone script
Pancakeswap clone script
Binance Clone script
Defi Clone Script
Decentralized Finance Defi Wallet Development
NFT Launchpad Development
NFT Ticketing Marketplace Development
White Label NFT Marketplace
Enterprise Blockchain Solutions
Uniswap Clone Script
Pancakeswap Clone Script
NFT Marketplace Development
Hire Metaverse Developers
Centralized Cryptocurrency Exchange Development
Coin base Clone Script
Hire Metaverse Developers
NFT Game Development company
Nice
Henrico Traffic Lawyer
Traffic Lawyer Henrico , VA
p2p cryptocurrency exchange development
cryptocurrency exchange development
Cryptocurrency exchange script
P2P crypto exchange script
Paxful clone script
DeFi Development Company"
That was a very usefull information, thank you for such an awesome information, Checkout our Binance Clone App Development
paxful clone script
ethereum smart contract audit
Great article so far!
Really enjoyed to read the content.
As a tech enthusiast, I always enjoy inspiring about the latest advancements in the industry.
Speaking of useful fintech business tools and app development service, have you checked out opris binance clone script. It's a powerful solution that can help businesses launch their own crypto exchange platform quickly and easily.
Keep your good work.
Cheers!
smart contract auditing services
Thanks for sharing valuable information, I really very impressed with your blog. have a look on coinbase clone script
Thanks for sharing this Informative Post!!!
White Label NFT Marketplace Development
Cryptocurrency Exchange Script
Benefits of cryptocurrency exchange script
binance clone script V2.0 enhanced
Crypto Exchange Software
Cryptocurrency Exchange Script
binance clone Software
bitcoin Exchange Script
binance clone Script
Wow, I want to salute you. Is a very good comment & very informative as well.
BC.Game Script
AI Game Development
NFT Marketplace
Web3 Wallet Development
Whitelabel Crypto Exchange Development
Whitelabel Crypto Exchange Development
White label NFT marketplace Development
Black friday 2023
Blockchain casino game Clone Script
Bitcoin harving 2024
crypto casino game development
NFT game development company
metaverse game development company
Bc.game clone script
crypto casino script
Stake alternative
Binance clone script
Onlyfans clone script
Cash app clone script
Nice blog. Thanks to share this informative content with us. Its very helpful content.
Specializing in sports betting software development company, they create tailored solutions that drive engagement and enhance user experiences. Their expertise lies in delivering secure, dynamic, and user-friendly platforms that cater to the evolving demands of the sports betting industry.
thank's for content!
Crypto Marketing Agency
natural supplments
BizVertex is a leading ICO marketing agency offering comprehensive solutions to boost your Initial Coin Offering. Our expert team provides strategic marketing, PR, and community management to ensure your ICO gains maximum visibility and success. Partner with BizVertex for tailored ICO campaigns that drive investor interest and grow your crypto project.
To know more:
Call / whatsapp: 918807211121
Telegram: Bizvertex
Post a Comment