Sunday, July 10, 2011

Generating Permutation with Javascript

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.

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  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.
  3. Swap a[k] with a[l].
  4. 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, also serve as a user guide :)



/////////////////////////////////////////////
// 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:

Max Roald Eckardt said...
This comment has been removed by the author.
Max Roald Eckardt said...

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?

Anonymous said...

Really Good blog post.provided a helpful programs for generating permutation with javascript. keep updating...
Digital marketing company in Chennai

Ancy merina said...
This comment has been removed by the author.
New Year Love 2019 said...

https://newyear2019love.com/ wishes for new year

Anonymous said...

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

Live PSL Digital said...

PSL T20 Live streaming for all matches

Happy Valentines Day 2k19 said...

https://happyvalentinesday2019.net/ best quotes for lover

Mr. Ronan Melone said...

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

mesotheliama said...

https://teacherappreciationweekideas.com best way to know

jhoni said...

best way to know

pip camera new version 2019

El Clasico said...

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/

jhoni said...

best way to know

Sketch Maker new version 2019

Happy Valentines Day 14 said...

Free download valentine's day ecards

Varun g said...

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.









Happy Valentines Day 14 said...

valentine's day movie quotes movie funny quotes

HemanthSai said...

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

Unknown said...

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

Dale Morris said...

Norton antivirus phone number
McAfee support number
Malwarebytes customer support number
Hp printer support chat
Canon printer customer support number

Chiến SEOCAM said...

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

Anonymous said...

Kursus Indonesia
Kursus Indonesia
Kursus Indonesia
Konslet
Memory Card
Konektor Charger
Firmware Android
Imei Null
Octoplus Samsung

Anonymous said...

Baterai Tanam
Service Electronic
Handphone Error
ZTE Huawei
LCD Warna Warni
Freelance
Xiaomi
Port USB

Anonymous said...

Komponen HP
Cara Menghidupkan HP Mati Total Baterai Tanam
Macam Macam IC
Cara Memperbaiki LCD
Tombol Volume
Lembaga Kursus Terbaik Indonesia
Imei
Baterai

cbseguru said...

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.

Anonymous said...

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

delhi meraki said...

Very nice blgo, you are sharing very nice information,


if someone here looking for awesome stories to read kindly visit my website DelhiMeraki

Fuel Digital Marketing said...

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.

Buy Instagram Followers Paytm said...

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

Buy instagram followers India said...

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

Anonymous said...

Cryptocurrency Exchange Software Development
Binance Clone Script
DeFi Development Company
DeFi Staking Development
Uniswap Clone

Anonymous said...

PancakeSwap Clone Script

Anonymous said...

Binance Smart Chain Development

Anonymous said...

Cryptocurrency Exchange Script
Uniswap Clone Script
Binance Clone Script

Anonymous said...

1Inch Exchange Clone Script
White Label Crypto Exchange
Binance Smart Chain Token Development
Cryptocurrency Exchange Development Company

Consultant @ Blockchain Apps Developer said...

TokenMint Clone Script

Consultant @ Blockchain Apps Developer said...

Bep20 Token Development Company

Consultant @ Blockchain Apps Developer said...

Ethereum Exchange Script

smmshop99.com said...

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

Tim Josh said...

BEP20 Token Development Company
NFT Marketplace Development Company

Tim Josh said...

Blockchain Development Company
NFT Marketplace Clone Script Providers

Tim Josh said...
This comment has been removed by the author.
Anonymous said...

On demand app development company

Anonymous said...

Pancakeswap Clone Script
Binance Clone Script

jackbrowny said...

Nice informative written!

Oliver Lucas 2021 Years Blog Sections said...

BEP20 token development company

Oliver Lucas 2021 Years Blog Sections said...

NFT Marketplace Development

Emily Jacob said...

A good article

Binance clone said...

great insight

Pixel Studios said...

Thanks for sharing valuable information, I really very impressed with your blog.
Ecommerce Web Development Company In Chennai
Ecommerce Web Development In Chennai

Xia George said...

Pancakeswap Clone Script
Pancakeswap Clone Software
Pancakeswap Clone Development
Pantherswap Clone Script
Pantherswap Clone Software
Pantherswap Clone Development

unknown said...

Decentralized exchange script
Decentralized exchange software

Zodeak said...

Binance Clone Script

Cryptocurrency Exchange Script

P2P Cryptocurrency Exchange Script

Genius said...

BEP20 token generator

blockchainx

Developcoins said...

Uniswap Clone Script

James Peter said...

Thanks,
GloriaFood Alternative Solution

savingchief said...

Thanks for this amazing post.
Visit:-
considir
bitrated
hydroshare.org
emdr-mn
ebluejay

Zaara Hary said...

Axie Infinity Clone Script
Uniswap Clone Script
Binance Clone Script
PancakeSwap Clone Script
NFT Marketplace Development

Shirley Eva said...

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

Blockchainkicks said...

Crypto Staking

Shirley Eva said...

Uniswap clone script

Consultant @ Blockchain Apps Developer said...

NFT Marketplace Development Company

Tom-shelby said...

PancakeSwap Clone Script
DeFi Development Services

Bajeelaaluin Tech Blog said...

Thank you share the gratefulness post
Axie infinity clone script

Genius said...

Thank you for sharing this valuable post!
- BEP20 token generator

Consultant @ Blockchain Apps Developer said...

NFT Marketplace Development Company
White Label NFT Marketplace Development Company
Opensea Clone Script

Didaagnew said...

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

Shirley Eva said...

Defi development company
Trust wallet clone
Uniswap clone

Bitdeal said...

NFT Gaming Platform Development
Uniswap Clone Script
Pancakeswap Clone Script
DeFi Development Company

Nithi said...

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

Consultant @ Blockchain Apps Developer said...

CryptoPunks Clone Script

Alina Kennady said...

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

fernelisabeth said...

Valuable Post! thank You


Cointool App Clone Script |
Zed Run Clone Script
Token Generator Platform Development Company |
Crypto Punks Clone Script |

Bajeelaaluin Tech Blog said...

Zed Run Clone Script

fernelisabeth said...

Cointool App Clone Script |
Sorare Clone Script
Token Generator Platform Development Company |
Crypto Punks Clone Script |

Consultant @ Blockchain Apps Developer said...

Metaverse NFT Marketplace Development Company

Amritsar digital academy said...

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.

Bajeelaaluin Tech Blog said...

Thanks for sharing this Fantastic post!
Axie Infinity Clone Script

fernelisabeth said...

Thanks for sharing useful information. Keep it up
OpenSea Clone |
Axie Infinity Clone |
Zed Run Clone
Decentraland Clone
Cointool App Clone |

Bajeelaaluin Tech Blog said...

Nice Blog
Zed run clone script

Eva Jo said...

Token Development |
Ethereum Token Development Company |
NFT Token Development Company |
DeFi Token Development Company |
Smart Contract Development Company |
BEP20 Token Development Company |

fernelisabeth said...

This is a nice Post!
TinyHero Clone |
OpenSea Clone |
Axie Infinity Clone |
Zed Run Clone
Cointool App Clone |

fernelisabeth said...

Excellent Post!
OpenSea Clone |
NBA Top Shot Clone |
Sorare Clone |
Cryptopunks Clone |
Axie Infinity Clone |
Zed Run Clone |

Bajeelaaluin Tech Blog said...

Amazing blog post!
OpenSea Clone Script

Bajeelaaluin Tech Blog said...

Opensea clone script
Axie infinity clone script
Rarible clone script
Zed run clone script
Cryptopunks clone script

Yara Niamh said...

cryptocurrency exchange software development
cryptocurrency exchange software development company

Anonymous said...

NFT Gaming Platform Development
Uniswap Clone Script
Pancakeswap Clone Script
Decentraland Clone Script
Axie Infinity Clone Script
DeFi Development Company

Nethrasingh said...

Sandbox Clone Script
Opensea Clone Script

Tom-shelby said...

Decentralized Exchange Script
DeFi Development Services

Bajeelaaluin Tech Blog said...

Amazing post, thanks for sharing

Opensea clone script

Decentraland Clone Script

Praveen Kaur said...

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.

Bajeelaaluin Tech Blog said...

NFT Marketplace Development Company
Decentraland clone script
Opensea clone script
Rarible clone script
Axie infinity clone script
Zed run clone script

Yara Niamh said...

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

Bajeelaaluin Tech Blog said...

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

Henry said...

Token Development |
Token Development Services
Cryptocurrency Development Services
ERC20 Token Development Company |
ICO Development Company |
White Paper Writing Services |

Bitcoin exchange business solutions said...

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

parker said...

Nice article to read!

Trust Wallet Clone Script

Cryptocurrency Wallet Company

Bajeelaaluin Tech Blog said...

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

Bajeelaaluin Tech Blog said...

GameFi clone script
Sandbox clone script
NFT Marketplace Development Company
Axie infinity clone script
Zed run clone script
Opensea clone script

Anonymous said...

Blockchain Development Services
Blockchain Firm provides reliable and custom blockchain development services for large enterprises and medium business organizations
Blockchain development services

charly manrtin said...

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

elon said...

kraken clone script

Isabellanoviya said...

NFT Game Development Company

Axie Infinity Clone Script

Zed run clone script

Cryptokitties clone script

Isabella Jacob said...

Trustwallet clone script
DeFi Development
Pancakeswap Clone script

Bajeelaaluin Tech Blog said...

NFT Marketplace Development Company
Metaverse Development Company

Bajeelaaluin Tech Blog said...

white Label Crypto Exchange Software
BEP20 Token Development
NFT Minting Platform Development Company

Sanaa said...

Solana Token Development Company
ERC20 Token Development Company
Smart Contract Development Company
NFT Token Development Company
Polygon Token Development Company

Anonymous said...

DeFi Development Company
Pancakeswap Clone Script
DeFi Staking Platform Development
Trustwallet Clone App

Bajeelaaluin Tech Blog said...

Excellent post, thanks for sharing
Cryptocurrency Exchange Software Development
NFT Marketplace Development Company

World Scouter said...

Thanks you for sharing this unique useful information content with us. Really awesome work. keep on blogging
Teen Patti Game Development Company

Jenifergroves said...

Pancakeswap clone script

Wazirx clone script

Cryptocurrency exchange development company

LocalBitcoins clone script

Bajeelaaluin Tech Blog said...

NFT Marketplace Development Company
Binance Clone Script
NFT Development Company

Ellyseperry said...

BEP20 Token Development Services
BEP20 Token Development agency

BlockchainX said...

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.

Anonymous said...

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

Nodalsoft Blogs said...

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

Bajeelaaluin Tech Blog said...

NFT Marketplace Development Company
Opensea clone script
Pancakeswap clone script
Binance Clone script
Defi Clone Script
Decentralized Finance Defi Wallet Development

Erikavanessa said...

NFT Launchpad Development
NFT Ticketing Marketplace Development

Anonymous said...

White Label NFT Marketplace
Enterprise Blockchain Solutions
Uniswap Clone Script
Pancakeswap Clone Script

Erikavanessa said...

NFT Marketplace Development
Hire Metaverse Developers

George Patrick said...

Centralized Cryptocurrency Exchange Development
Coin base Clone Script

Erikavanessa said...

Hire Metaverse Developers
NFT Game Development company

srislaw said...

Nice

Henrico Traffic Lawyer
Traffic Lawyer Henrico , VA

elon said...

p2p cryptocurrency exchange development

Eisensara said...

cryptocurrency exchange development
Cryptocurrency exchange script
P2P crypto exchange script
Paxful clone script

caroline said...



DeFi Development Company"

Anderson Royce said...

That was a very usefull information, thank you for such an awesome information, Checkout our Binance Clone App Development
paxful clone script

Cyphershieldtech said...

ethereum smart contract audit

Opris Exchange said...

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!

Cyphershieldtech said...

smart contract auditing services

David said...

Thanks for sharing valuable information, I really very impressed with your blog. have a look on coinbase clone script

Andrew Charles said...

Thanks for sharing this Informative Post!!!

White Label NFT Marketplace Development
Cryptocurrency Exchange Script

blockchain development said...

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

kester said...

Wow, I want to salute you. Is a very good comment & very informative as well.
BC.Game Script

AI Game Development

NFT Marketplace

Eleanorsophia said...


Web3 Wallet Development
Whitelabel Crypto Exchange Development

Eleanorsophia said...

Whitelabel Crypto Exchange Development
White label NFT marketplace Development
Black friday 2023

cryptocurrency said...

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

Bharathi said...

Binance clone script
Onlyfans clone script
Cash app clone script

sports betting software developer said...

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.

tobygarfield said...


thank's for content!



Crypto Marketing Agency

charliekyle said...

natural supplments

kimiko said...

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