DEV Community: Snehit Sah

Generating Combinations using C++

Snehit Sah — Fri, 23 Jul 2021 12:01:09 +0000

Introduction

The task for this post is to help you understand how to generate combinations of size r using numbers from 1 to n and then extend that code to generate combinations for any set of objects.

When I say n = 5 and r = 3, it means we are dealing with the first five natural numbers to generate combinations of size 3.

Understanding Combinations

We shall be generating combinations in lexicographic order. Also, since combination does not concern itself with the relative order the chosen elements are arranged in, we shall always be having our chosen elements in lexicographical order too.

The first combination we choose has to be the first r elements when the n objects are sorted. This is because it gives us the lexicographically smallest word with the individual elements themselves in lexicographical order too. (basically, the if all combinations were arranged in a dictionary, then we want to start with the first one) So, in case of n = 5 and r = 3, the first combination is 123.

Now, think what should be the last combination. I propose that it will be the last r elements when the n objects are sorted. Why should it be? When we are generating combinations in lexicographical order, each combination should have a greater position in a dictionary. So the last combination should have the greatest elements from given objects. The chosen elements themselves should also be in lexicographical order.

The knowledge of last combination also gives us an interesting observation. The maximum value at a given index idx can be n - r + idx + 1, where index starts from zero. This is necessary to maintain the dictionary order of individual elements in a combination.

Take for example the case of n = 5 and r = 3. If we position the number 5 at index 1, then the combination will look like X5_, where X may be any number lower than 5. The blank at third position should have a number greater than 5 if we are to maintain dictionary order. But placing 6 there is not possible since we only have 5 elements. According to the formula n - r + idx + 1, the maximum value at third position (or second index) can be 4.

Another thing to note is that every time we increment a position, we need to set the elements to its right as one more than its left neighbor. This will be clear when I discuss the code.

Formal Algorithm

fun next_combination :
    parameters: integer n - max objects available
                integer r - size of chosen set
                array curr_comb - denoting
                  current combination of r elements
                integer idx - index to increment

    return:     true if next combination exists
                  curr_comb is updated in place
                  with the next combination
                false if last combination is provided
    ____

    if idx < 0 :
        return false

    if curr_comb[idx] < n - r + idx + 1 :
        ++curr_comb[idx]
        for i in (idx + 1, n - 1):
            curr_comb[i] = curr_comb[i - 1]
        return true

    else :
        return next_combinaition(n, r, curr_comb, idx - 1)

For this function to work, it should be called with idx as r - 1, since we want to start incrementing from last index. This code first check if the index to increment is less than 0. If yes, it means that the next combination does not exist, or in other words, we are already at last combination.

Then it checks if the value at curr_comb[idx] is less than its maximum permissible value. If yes, then it increments the value at idx and sets its following elements as one plus their left neighbor.

If the value it idx is already the maximum allowed, then the function recursively calls itself with same parameters, but idx decremented by one. This continues till either the next combination is found, or the function is called with idx less than zero, in that case next combination does not exist.

The function is recursive, so it must pass the sanity test. Does it stop recursing at some point? Each recursive call decrements idx by 1. Eventually, idx will be less than zero, in which case the function will no longer recurse. So, it is guaranteed that the function does not recurse indefinitely.

C++ Code

void increment_neighbor(std::vector<int> &arr, int idx)
{

    for (int i = idx; i < arr.size(); ++i)
        arr.at(i) = arr.at(i - 1) + 1;
}

bool _next_combination(int n, int r, std::vector<int> &curr_comb,
                       int idx)
{

    if (idx < 0)
        return false;

    if (curr_comb.at(idx) < n - r + idx + 1) {
        ++curr_comb.at(idx);
        increment_neighbor(curr_comb, idx + 1);
        return true;
    }
    else
        return _next_combination(n, r, curr_comb, idx - 1);
}

bool next_combination(int n, int r, std::vector<int> &curr_comb)
{

    return _next_combination(n, r, curr_comb, r - 1);
}

Following are the required includes:

#include <algorithm>
#include <utility>
#include <vector>

This code is a direct implementation of the algorithm I shared above. The part that increments the neighbors by 1 has been extracted to its own function called increment_neighbor.

You might ask, why are there two functions named next_combination, one with a preceding underscore. The goal of a good interface is to be as simple as possible. In the recursive function, we initially call it with idx = r - 1. For a programmer reusing our function, it may be tedious to pass the fourth parameter, when it can be simply deduced from the third second one.

So, we create a helper function that takes the three required parameters and calls the original recursive function with fourth parameter set.

Using Our Function

int main()
{

    int n = 0, r = 0;

    // take input for n and r

    std::cout << "Enter r individual elements (integers) of"
                 " current combination separated by spaces\n";

    std::vector<int> numbers(r);

    for (int i = 0; i < r; ++i)
        std::cin >> numbers.at(i);

    if (next_combination(n, r, numbers)) {
        std::cout << "Next combination is\n";
        for (auto x : numbers)
            std::cout << x << " ";
        std::cout << "\n";
    }
    else {
        std::cout << "The input is already the final combination\n";
    }

    return 0;
}

This code will simply check if next_combination return true or false. If true, it means that the next combination was found and it is printed. Otherwise, inform user that we are already at last combination.

To generate all combination, use the following snippet.

std::vector<int> numbers(r);

for (int i = 1; i <= n; ++i)
    numbers.at(i) = i;

do {
    for (auto x : numbers)
        std::cout << x << " ";
    std::cout << "\n";
} while (next_combination(n, r, numbers));

Running on Custom Elements

Lets say the user does not want to generate combination of numbers, but instead wants to generate combinations of a custom set of objects. The object can be anything - character, string, struct etc.

The basic idea is to store the n individual elements in an array. Generate the combination on numbers from 1 to n as we did earlier. But while printing the combination, instead of number, print the element at that position.

As an example, here is the snippet for generating combinations of words.

std::vector<int> numbers(r);
std::vector<int> words(r);

for (int i = 1; i <= n; ++i)
    numbers.at(i) = i;

std::cout << "Enter n individual elements (words)"
                " separated by spaces\n";

for (int i = 0; i < n; ++i)
    std::cin >> words.at(i);

do {
    for (auto x : numbers)
        std::cout << word.at(x) << " ";
    std::cout << "\n";
} while (next_combination(n, r, numbers));

Memoization

Recursive algorithms can be made much faster when using memoization. Do we need memoization?

Memoization helps when the function is called with the same parameters multiple times. By storing intermediate results, it does not need to do computations if the parameters provided are not new.

In our function, n and r are constant throughout. idx changes its value, but it does so in a very small range. So there seems to be lot af scope for repetition of parameters. However, the parameter curr_comb does not repeat. Each combination is different. When recursing with the same combination, then the value of idx is guaranteed to change.

So we need not use memoization, as the intermediate values are never reused.

Thanks for reading! Share your feedback in the comments <3

You can follow my personal blog at https://flyingcakes85.github.io/blog/

Follow me on GitHub : flyingcakes85

Fixing Jekyll/Webrick Issue on Arch Linux

Snehit Sah — Mon, 24 May 2021 11:42:46 +0000

Jekyll may not run on Arch Linux because of an error with webrick. This is caused because webrick is not yet compatible with latest version of Ruby (3.0.1).

This is the relevant line from error output.

/blog/vendor/bundle/ruby/3.0.0/gems/jekyll-4.2.0/lib/jekyll/commands/serve/servlet.rb:3:in require: cannot load such file -- webrick (LoadError)

While setting up my GitHub pages blog, I faced this issue. I'll quickly document how to fix this.

Install Bundle

You will need to have rubygems installed for this.

sudo pacman -S rubygems

Then install bundle via gem.

gem install bundle

Gem will print a warning about not having the local binary folder in your path. Add the following line to your ~/.bashrc or ~/.zshrc depending on the shell you use.

export PATH=/home/$USER/.local/share/gem/ruby/3.0.0/bin:$PATH

Make sure you replace "3.0.0" with the version number gem reports.

Uninstall Ruby

We need to remove the latest Ruby version.

sudo pacman -Rns ruby rubygems

Install Ruby 2.7

Webrick is compatible with Ruby 2.7. This is the version we will install.

sudo pacman -S ruby2.7

Symlink `ruby` Binary

bundle will call the binary at /usr/bin/ruby. However, the old Ruby version is installed at /usr/bin/ruby-2.7. So we will create a symlink. You will need to uninstall ruby as I said earlier.

sudo ln -s /usr/bin/ruby-2.7 /usr/bin/ruby

Now, /usr/bin/ruby will just be a symlink (or shortcut in layman terms) to /usr/bin/ruby-2.7.

Run `bundle`

Go to your Jekyll project directory. Install the dependencies.

bundle install

Then launch your Jekyll site

bundle exec jekyll serve

Your website should be now live! 🚀

You can follow my personal blog at https://flyingcakes85.github.io/blog/

Follow me on GitHub : flyingcakes85

Beginner's Guide To Shell Aliases With Examples

Snehit Sah — Mon, 24 May 2021 07:09:42 +0000

Introduction

*nix shell is a powerful tool that can help you go about your work easily. At the lowest level, it can be It can seamlessly run binaries and this power combined with shell grammar, you can write scripts to automate processes on your system.

Shell has this feature where you can define aliases to existing commands. So, if I alias w to wget, then every time I run w, it will be interpreted as wget.

Defining Aliases

Shell aliases can be easily defined by the following syntax:

alias <keyword>="some long command"

So, for the above example, I can write

alias w="wget"

This line goes in your ~/.bashrc or ~/.zshrc depending on the shell you use. After adding an alias, you need to reload your shell config. This can be done simply by restarting your teminal, or if you don't want to close the current running terminal, you can run the following command:

source ~/.zshrc   # bash users replace with ~/.bashrc

Some Useful Aliases I Keep

Text Editor

alias n="nvim"

I am quite often in the terminal messing with configuration files and all, meaning I regularly open the text editor. So, I created a single character alias to launch nvim.

Git Commands

I alias the common Git commands. Some people like to go overboard and add lots of Git related aliases. Do whatever you are comfortable with.

alias gcm="git checkout main"
alias gp="git pull"
alias gpu="git push"

Aliases for Development Tools

I first did this when I was learning Rust.

alias ccl="cargo clean"  # cc conflicts with gcc/cc
alias cch="cargo check"
alias cb="cargo build"
alias cr="cargo run"
alias ca="cargo add"
alias rn="rustup override set nightly"

You can set aliases for whichever language or build tools you generally use.

`ls` commands

alias l="ls -alh --color=tty"
alias ls="ls --color=tty"

I simply use l to list files in long format.

cat -> bat

alias cat="bat"

bat is a cat clone with host of new features. The major reason why I use bat is the syntax highlight and line numbering. Using Linux distros for a few years now, I am used to running cat in the terminal, so I aliased it to bat.

Clear Terminal

alias c="clear"

Yes I am too lazy to type clear so I aliased it to c.

Copy to Clipboard

alias cpy="xclip -sel clip"

Often you need to copy the output of a command on to the clipboard. If the output is short, you can use your mouse to select text and press Ctrl+Shift+C. However, if the output is long, good luck copying it.

With the above alias, I pipe the output of a command to cpy and it will be copied on to the clipboard.

inxi -F | cpy   # output of inxi -F is copied to clipboard

Youtube-dl Command

alias ytmp3="youtube-dl --extract-audio --audio-format mp3 --audio-quality 256K --add-metadata --metadata-from-title \"%(artist)s - %(title)s\" -o \"%(title)s.%(ext)s\""

This downloads the audio stream from the supplied link and add metadata to file in Artist - Title format.

Conclusion

These were just some examples of the aliases I use. You can set more such aliases to make your workflow faster.

You can follow my personal blog at https://flyingcakes85.github.io/blog/

Follow me on GitHub : flyingcakes85

Cover photo by Anete Lusina from Pexels

Switching to Programmer Dvorak - 3 Months Later

Snehit Sah — Mon, 24 May 2021 02:25:00 +0000

I've been trying to learn touch typing for long. Like most people, I practiced on qwerty, but could never actually touch type with confidence.

First time I touch typed, I was in third grade. As a part of the computer club, I had to type out a children's book into MS Word and then copy paste the text into Windows Movie Maker to make a short video with the text and pictures. That ended up being my last touch with touch typing for ten years.

Start Fresh

In 2020, I decided to learn touch typing, no matter what! Easy thing to say, but after typing for ten years by looking at the keyboard, I couldn't get rid of that habit. Looking back, I felt this was an investment I was too lazy to
do. During my school days, I learnt basic C++, did some competitive coding, did lot of HTML and CSS, typed many many documents and even got Microsoft Office Specialist Certification - all via hunting and pecking on the keyboard.

Old habits are tough to change. I practiced on qwerty, and reached a tiny 40wpm.

Switching to new layout

A random user on a discord server suggested me to try out an alternative layout so that looking at the keyboard becomes futile. The idea resonated with me. Up until then, I never considered using an alternate layout.

I looked up on the net, and found that Dvorak kinda fit my needs. Claimed to be comfortable. Common alphabets placed on the home row. And right hand has more movement than the left, which is good for right handed people like me.

I started practicing on this website called learn.dvorak.nl. The website does not require you to change your layout from system settings. Instead, the website remaps keys based on input from your qwerty input. Of course, you can disable that feature if you have changed to Dvorak from system settings.

Enter Programmer Edition

About two weeks later, I was comfortable typing on Dvorak keyboard. As they claimed, it was easy to learn. I wasn't a fast typer by any measure, but at least the keys were memorized and I could type without looking at the keyboard - even if it was at 15wpm. I decided I was ready to switch to Dvorak full time.

I went to the Arch Wiki to know how to change my layout. There I found another Dvorak based layout - Programmer Dvorak. The idea behind this layout was to place the common symbols used in programming on the top number row, and have them inserted without pressing Shift. The numbers need to be inserted with Shift key combination. Alphabets were in their right locations as they are on Simplified Dvorak.

This layout, for obvious reasons, immediately appealed to me. I started using it right away.

Experience

I get the typing benefits of Dvorak, which are great by the way. I feel less hand movement as compared to my Qwerty touch typing sessions. Layout makes sense, although I am not a fan of positioning the letter l where it is.

The layout is comfortable too. My wrists don't curse me anymore when I am typing for long hours.

Having symbols on the top row makes them easily accessible. I am surprised by the fact that I am now happily typing out symbols while coding without requiring to press Shift.

Bottom line

Simplified Dvorak is good for all practical purposes. Programmer Dvorak comes with a small problem that the numbers on top row are not in increasing order. Typing numbers has been a severe pain for me, and those who watched me live stream my code often asked me why I was typing wrong whenever I had to type a number.

I faced another crisis when I gave my programming test at university. They had Windows computer, and I wasn't allowed to use my laptop to give the test. Dvorak is a universal layout which you will find on all modern operating systems. However, Programmer Dvorak is not universal, meaning I did not have that for my exam. Alphabets were easy to type, but typing symbols - which you do after almost every word - was a serious pain. I suffered the torture for the first task and switched to Qwerty for my second task. Hunt and peck is more efficient than pressing random keys and hoping they are correct.

Conclusion

If you are happy with your current layout, continue with it by all means. However, even if there's a tiny bit of curiosity in you to try out alternate layouts, then make sure you experiment.

If you want to be able to type on any computer - in case you type on other's systems often - then Simplified Dvorak is the best option. If you want Dvorak but are mostly typing on your own system (like me) do consider Programmer Dvorak.

If you don't mind using a non-universal layout, then there is Colemak layout, which looks quite impressive. Its easy to transition from Qwerty to Colemak. And reading up on their website, it certainly is worth trying.

For me, I am happy with Programmer Dvorak and am going to continue with it.

You can follow my personal blog at https://flyingcakes85.github.io/blog/

Follow me on GitHub : flyingcakes85

Cover photo by John Petalcurin from Pexels

Arch Linux Package Management Beginner's Cheat Sheet

Snehit Sah — Sun, 23 May 2021 14:34:27 +0000

Introduction

Arch Linux comes with a powerful package manager called pacman. Often new users take time to figure out its commands because it does not have the usual 'obvious' commands like apt. So here is a short post about pacman commands.

Note : All pacman commands need to be run with superuser privileges. You need to prepend the commands with sudo for them to work. For the sake of brevity, I have omitted sudo.

Installing Packages

Download and Install

-S flag asks pacman to synchronize packages.

pacman -S package1 package2 package3

will download install specified packages along with their necessary dependencies.

Selecting Repo in Case of Multiple Providers

By default, package is searched in repos in the order they are listed in /etc/pacman.conf.

In case a package is available from more than one source, then you can specify the repo name before package name to select the repo you want to download the package from. For example, I am using Endeavour OS, with Chaotic AUR added to my repo list. So, I can get the polybar package from two sources - EndeavourOS reop and Chaotic AUR repo. Since Endeavour OS repo has a preference in my pacman.conf, pacman will download polybar from that repo. However, if I want to download it from Chaotic AUR, I can run the following command.

pacman -S chaotic-aur/polybar

Updating Packages

pacman -Syu

will download new package database and then install the packages that have new updates available. This will include your kernel and other core packages too so make sure you have backups ready in case something goes wrong. Timeshift is a popular backup tool.

Searching For a Package

pacman -Ss search terms

will search for the supplied terms and provide you with a list of matching entries.

Download But Don't Install

You may want to download packages, but not install them right away. This can be done by using the -w flag with one of the sync commands.

pacman -Sw reflector   # downloads reflector but doesn't install it
pacman -Syuw   # downloads available updates but doesn't install them

About `-Syy`, `-Sy` and `-Syuu`

I edited this post and added this section because this deserves some attention. New users often use -Syyu to update packages. This is not a good practice, since if you frequently update, it will put extra load on the mirrors.

-Sy will update only those repos that are outdated. -Syy will force update all repos even if they are up to date. So avoid using -Syy. It is meant to be used in case your packaged database is corrupted or has some other issue.

Similarly, -Syuu will force package version to be in sync with the repo. In case your mirror has an outdated version of a package, it will be forcefully downgraded. Use -Syu to update packages.

And finally, never use -Sy alone. On Arch Linux, partial upgrades are not supported. If you do -Sy and then install a package, you will run into a case of partial upgrade and that may lead to problems.

In short, use -S to install and -Syu to update.

Details for a package

pacman -Si package-name

will show details for the supplied package name.

Removing packages

Remove a Package

pacman -R package1 package2 package3

will remove the specified packages.

Remove along with unneeded dependencies

pacman -Rs package1 package2 package3

-s flag instructs pacman to remove any dependencies of the specified packages, that are no longer required by any other package on the system.

Removing groups of packages

pacman -Rsu gnome

will remove the gnome group, but preserve any packages that are required by one or more packages installed on the system.

Query commands

List of installed packages

pacman -Q

will output the list of installed packages along with their versions.

List packages no longer needed

If you remove packages without using the -s command, then unneeded dependencies can pile up on your system. You can list them with the following command

pacman -Qdtq

To uninstall them, simply pipe them to pacman -Rs in with the following command

pacman -Qdtq | pacman -Rs -

Packages no longer part of any repository

Sometimes, when a package is no longer maintained, it is removed from repositories. You may want to remove them since they are most certainly no longer required

pacman -Qm   # list foreign packages
pacman -Qmq | pacman -Rs -    # remove foreign packages

Details for a package

pacman -Qi package-name

will display information for a the supplied package name. Note that this works only for installed packages.

Know owner of a file

In case a system file is damaged, reinstalling the relevant package may help you fix it. In such case, you need to know which package owns the file in question.

pacman -Qo /usr/bin/zsh

This command tells me package that owns the file I specified.

List explicitly installed packages

To get the list of package installed explicitly, meaning they are not installed as dependencies, run the following command

pacman -Qe

The "explicitly installed" tag can be modified as described here.

List packages installed as dependency

To get the packages that were installed as a dependency, run the following command

pacman -Qd

Again, this tag can be modified as described here.

Verify packages

pacman -Qk

This will check if all the files for the installed packages are available on the system.

Database commands

Mark a package as explicitly installed

pacman -D --asexplicit package-name

This will mark the package as explicitly installed and this package won't be considered when you run pacman -Qdtq or remove commands unless you explicitly specify the package name as a candidate for removal.

Mark a package as dependency

pacman -S --asdeps package-name

Works as totally reverse of the previous command. Specified package will be considered for removal and also as unneeded dependency if no package depends on it.

File commands

List files installed by a package

pacman -Fl package-name

will show the list of files that a package will install onto your system.

Search for file or filepaths

pacman -F filename

will search for filename and list the packages that provide a file by that name. This is specially useful when I need to know which package provides a specific header file I need to use.

-F only accepts complete filenames, without path. To do a regex search, with filepaths and partial names, use the -x flag.

pacman -Fx path/to/file

Conclusion

Thats all for this post.

You can follow my personal blog at https://flyingcakes85.github.io/blog/

Follow me on GitHub : flyingcakes85

DEV Community: Snehit Sah

Generating Combinations using C++

Introduction

Understanding Combinations

Formal Algorithm

C++ Code

Using Our Function

Running on Custom Elements

Memoization

Fixing Jekyll/Webrick Issue on Arch Linux

Install Bundle

Uninstall Ruby

Install Ruby 2.7

Symlink ruby Binary

Run bundle

Beginner's Guide To Shell Aliases With Examples

Introduction

Defining Aliases

Some Useful Aliases I Keep

Text Editor

Git Commands

Aliases for Development Tools

ls commands

cat -> bat

Clear Terminal

Copy to Clipboard

Youtube-dl Command

Conclusion

Switching to Programmer Dvorak - 3 Months Later

Start Fresh

Switching to new layout

Enter Programmer Edition

Experience

Bottom line

Conclusion

Arch Linux Package Management Beginner's Cheat Sheet

Introduction

Installing Packages

Download and Install

Selecting Repo in Case of Multiple Providers

Updating Packages

Searching For a Package

Download But Don't Install

About -Syy, -Sy and -Syuu

Details for a package

Removing packages

Remove a Package

Remove along with unneeded dependencies

Removing groups of packages

Query commands

List of installed packages

List packages no longer needed

Packages no longer part of any repository

Details for a package

Know owner of a file

List explicitly installed packages

List packages installed as dependency

Verify packages

Database commands

Mark a package as explicitly installed

Mark a package as dependency

File commands

List files installed by a package

Search for file or filepaths

Conclusion

Symlink `ruby` Binary

Run `bundle`

`ls` commands

About `-Syy`, `-Sy` and `-Syuu`