how to compute the required column width for the ls multi-columns display?

Question

when ls display a list of files, it display it in columns according to the terminal width, can I know what is the size of each columns?

Answer 1

Having a width of W, and having the N files to output. You can do a binary search to find the maximum number of columns.

You can assume 1 column is always possible (a file per line), and that N columns is not possible (technically, it is, when everything can be printed on a single line, but just for visualizing that the binary search applies).

Sample code:

#include <stdio.h>

#define N 12 // Number of files
#define W 80 // Terminal width

int can_be_printed(int *lengths, int columns)
{
    int lines = 1 + (N-1) / columns; // ceil(N / columns)
    for(int i=0; i<lines; i++)
    {
        int w = 0; // For the required line width
        w += lengths[i]; // First column
        for(int j=i+lines; j<N; j+=lines) // For each filename in the same line
            w += 2 + lengths[j]; // 2 is the space between filenames for the output
        if(w > W) // Required width is higher than terminal width
            return 0; // false
    }
    return 1; // true
}

int main()
{
    int file_lengths[N] = {7, 9, 9, 5, 6, 8, 9, 6, 7, 13, 6, 10};
    int low = 1; // Always possible
    int high = N; // Generally, not possible
    while(high - low > 1) // Perform binary search
    {
        int mid = (low + high)/2; // Cut in half
        int ans = can_be_printed(file_lengths, mid); // true or false
        if(ans) // If it's possible with the width mid
            low = mid;
        else
            high = mid;
    }
    int ans;
    if(can_be_printed(file_lengths, high)) // End BS picking the highest that is possible
        ans = high;
    else
        ans = low;
    printf("Maximum number of columns: %d\n", ans);
    return 0;
}